Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
Authors: Chi Jin
Qinghua Liu
Sobhan Miryoosefi
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: reinforcement learning theory
function approximation
Bellman Eluder dimension

Abstract: Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure—Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm— GOLF, and reanalyzes a hypothesis elimination-based algorithm—OLIVE (proposed in Jiang et al. (2017)). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.

Bellman Eluder Dimension: New Rich Classes of RL
Problems, and Sample-Efficient Algorithms
Chi Jin
Qinghua Liu
Princeton University chi wepijjeettooon..mmmmm edu
Princeton University
qinghual@princetonn.
Sobhan Miryoosefi
Princeton University
miryoosefi@cs
www.eeeiwwecc..ii.oooo.oooo princeton.edi
Abstract
Finding the minimal structural assumptions that empower sample-efficient learn- ing is of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by in- troducing new complexity measure Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but lim- ited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank prob- lems as well as low Eluder dimension problems. This paper further designs a new optimization-bnn based algorithm GOLF, and reanalyzes hypothesis elimination- OLIVE [proposed
1]. We prove that both algorithms learn the near-optimal policies of low BE dimension problems in number of sam- ples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.
based algorithm- -eeiit
1 Introduction
Modern Reinforcement Learning (RL) commonly engages practical problems with an enormous number of states, where Sunction approximation must be deployed approximate the true value function using functions from a prespecified function class. Function approximation, especially based on deep neural networks. lies at the heart the recent practical successes of RL in domains such as Atari [2]. Go [3], robotics [4], and dialogue systems [5].
Despite its empirical success, RL with function approximation raises challenges when comparing to the classic tabular RL: (1) generalization, to generalize knowledge from the visited states the unvisited states due to the enormous state space. (2) limited expressive- ness, to handle the complicated issues where true value functions or intermediate steps computed in the algorithm can be functions outside the prespecified function class. (3) exploration, address the tradeoff between exploration and exploitation when above challenges are present.
series of theoretical
Consequently, most existing theoretical results efficient RL with function approximation rely relatively strong structural assumptions. For instance, many require that the MDP admits a linear approximation [6-8], or that the model is precisely Linear Quadratic Regulator (LQR) [9-11]. Most of these structural assumptions rarely hold in practical applications. This naturally leads to one of the most fundamental questions in RL.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

low Bellman rank
low Bellman Eluder dimension
reactive PSRs
kernel reactive POMDPs
reactive POMDPs
L.QRs
low Eluder dimension
linear MDPs
generalized linear MDPs
kernel MDPs
tabular MDPs
Figure 1: schematic summarizing relations among families of RL problems'
What are the minimal structural assumptions that empower sample-efficient RL.
We advance our understanding of this grand question via the following two steps: (1) identify a rich class of RL problems (with weak structural assumptions) that cover many practical applications of interests; (2) design sample-efficien algorithms that provably learn any RL problem in this class.
The attempts find weak minimal structural assumptions that allow statistical learning can be traced in supervised learning where VC dimension [12] or Rademacher complexity [13] is proposed, in online learning where Littlestone dimension [14] sequential Rademacher complexity [15] is developed.
In the area of reinforcement learning, there are two intriguing lines of recent works that have made significant progress this direction. To begin with, Jiang et al. [1] introduces a generic complexity rank, which can be proved small for many RL problems including linear MDPs [7]. reactive POMDPs [16]. etc. [1] further propose an hypothesis climination- based algorithm- OLIVE for sample-efficiee learning of problems with low Bellman rank. On the other hand, recent work by Wang et al. [17] considers general function approximation with low Eluder dimension [18], and designs UCB-style algorithm with regret guarantee. Noticeably, generalized linear MDPs [6] and kernel MDPs (see Appendix C) are subclasses of low Eluder dimension problems, but not low Bellman rank.
In this paper, we make the following three contributions.
We introduce prove that the family of RL problems low BE dimension is remarkably rich, which subsumes both low Bellman rank problems and low Eluder dimension problems two arguably most generic tractable function classes so far in the literature (see Figure 1). The family of low BE dimension further includes problems such kernel reactive POMDPs (see Appendix C) which were not known to be sample-efficiently learnable.
complexity measure for RL Bellman Eluder (BE) dimension. We
We design a new optimization- optimal policies of low BE dimension problems in number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret or sample complexity guarantees match [8] which is minimax optimal when specified to the linear setting. Our rates further improve upon [1, 17] in low Bellman rank and low Eluder dimension settings, respectively.
algorithm-Gont
which provably learns near-
We reanalyze the hypothesis elimination based algorithm-OLvv proposed in [1]. We show it can also learn RL problems with low BE dimension sample-efficienll. under slightly weaker assumptions but with worse sample complexity comparing to GOLF.
1.1
Related works
This section reviews prior theoretical works on RL, under Markov Decision Process (MDP) models.
'The family of low Bellman rank problems and low Bellman Eluder dimension problems include both Q-type and V-type variants. Please refer to Section 3.1 and Appendix for more details.

---

We remark that there has been long line of research on function approximation in the batch RL setting [see, e.g., 19-22]. In this setting, agents are provided with exploratory data or simulator, so that they do not need to explicitly address the challenge of exploration. In this paper, we do not make such assumption, and attack the exploration problem directly. the following we focus exclusively on the RL results in the general setting where exploration is required.
Tabular RL. Tabular RL concerns MDPs with a small number of states and actions, which has been thoroughly studied in recent years [see, e.g., 23-30J. In the episodic setting with non-stationary dynamics, the best regret bound ((v H2 AT) is achieved by both model-based [27] and model- free [30] algorithms. Moreover, the bound is proved to be minimax-optimal [29, 31]. This minimax bound suggests that when the state-action space is enormous, RL is information-theoretilll hard without further structural assumptions.
RL with linear function approximation. A recent line of work studies RL with linear function approximation [see, e.g., 7, 6, 32, 8, 33-36] These papers assume certain completeness conditions, as well as the optimal value function can be well approximated by linear functions. Under one formulation of linear approximation, the minimax regret bound (dv/T) is achieved by algorithm ELEANOR [8], where d is the ambient dimension of the feature space.
RL with general function approximation. Beyond the linear setting, there is a flurry line of research studying RL with general function approximation [see, e.g., 37, 1, 36, 38, 17, 39, 40]. Among them, [1] and [17] are the closest to our work.
Jiang al. [1] propose complexity measure named Bellman rank and design an algorithm OLIVE with PAC guarantees for problems with low Bellman rank. We note that low Bellman rank is a special case of low BE dimension. When specialized to the low Bellman rank setting, our result for OLIVE exactly matches the guarantee in [1]. Our result for GOLF requires an additional complete- ness assumption, but provides sharper sample complexity guarantee.
Wang et al. [17] propose UCB-type algorithm with a regret guarantee under the assumption that the function class has low eluder dimension. Again, we will show that low Eluder dimension is special case of low BE dimension. Comparing to [17], our algorithm GOLF works under a weaker completeness assumption, with a better regret guarantee.
Finally, we remark that the algorithms proposed in [1, 33, 41] and this paper are all computationally inefficient in general. We notice several existing works [e.g., 7, 17] can be computationally efficient given suitable regression oracles but they require stronger representation conditions and also achieve worse regret guarantees.
Relation to bilinear classes class of RL problems-bllinee class with low effective dimension (also known as low critical infor- mation gain in Du et al. [41]). We comment on the similarities and differences between two works as follows.
Concurrent to this work, Du et al. [41] propose a new general tractable
In terms of algorithms, both Algorithm 2 in this paper and the algorithm proposed in Du et al. [41] are based on OLIVE originally proposed in Jiang et al. [1]. The two algorithms share similar guarantees in terms of assumptions and complexity results. More importantly, our work further develops a new type of algorithm for general function Ioproximation-Gonn can be viewed as an optimistic version of classical algorithm-Fitter Q- [42]. GOLF gives much sharper sample complexity guarantees compared to [41] for various settings, and is minimax- optimal when applied to the linear setting [8].
natural and clean algorithm which
In terms of richness of new classes identified, it depends on (a) what structure of MDP the com- plexity measures are applied to, and (b) what complexity measures are used. For (a), BE dimension applies to the Bellman error, while the bilinear class allows general surrogate losses of the Bellman error. For (b), this paper uses Eluder dimension while Du et al. [41] uses effective dimension. It can be shown that low effective dimension always implies low Eluder dimension (see Appendix C.2). In short, Du et al. [41] is more general in (a), while our work is more general in (b). As a result, neither work fully captures the other.
In particular, our BE framework covers a majority of the examples identified in Du et al. [41] includ- ing low occupancy complexity, linear Q* g/VV*, Q* state aggregation, feature selection/FL.AM
3

---

Nevertheless, our work can not address examples with mooell-basd function approximation (e.g., low witness rank [36]) while [41] can. On the other hand, Du al. [41] can not address the class of RL problems with low Eluder dimension [17] while our work can. Moreover, for several classes of RL problems that both works cover, our complexity measure is sharper. For example, in the setting of function approximation with generalized linear functions, the BE dimension is O(d) where is the ambient dimension of the feature vectors, while the effective dimension under the generalized bilinear framework of Du et al. [41] is at least (2(d²).
1.2 Paper organization
We present preliminaries in Section 2, the definition of Bellman-Fluder dimension as well as its relations to existing complexity notions in Section 3. We present the results for algorithm GOLF in Section 4, and conclude in Section 5. Due to space limit, we postpone the results for algorithm OLIVE to Appendix A. Further discussions on Q-type versus V-type variants of BE dimension, as well as the practical examples will provided Appendix and C. All the proof' are postponed to the appendix.
2 Preliminaries
We consider episodic Markov Decision Process (MDP), denoted by = (S, where S the state space, A the action space, H is the number of steps each episode, IP = (I&, hE((F) the collection of transition measures with PA (s' 8, a) equal the probability of transiting to s' after taking action a at state at the tth step. and = {rathe(m) is the collection of reward functions with r a) equal to the deterministic reward received after taking action a at state at the 1h step. Throughout this paper, we assume reward is non-negative, and Σ (n(8n, (n)) S for all possible sequence (81, 01,011.-. .1,,...,,881.. 88, 0.r).
In each episode, the agent starts at a fixed initial state Then, at each step h E [H]. the agent observes its current state 8h, takes action ah receives reward ra (5h, a;), and causes the environment to transit to 8h+1 ~ (- 5h, on). Without loss of generality, we assume there is terminating state Send which the environment will always transit at step H + and the episode terminates when Send is reached.
Policy and value functions A (deterministic) policy is collection of H functions {Th, S A) We denote VGr : + R as the value function at step h for policy т, so that (s) gives the expected sum of the remaining rewards received under policy x, starting from sh till the end of the episode. In symbol,
(s) == E. Σ (sw, anr) sh. = s].
Similarly, we denote Q7 x A + R as the Q-value function at step h for policy n, where
H (sw and) 8h. = On = a).
(x. = E.
There exists optimal policy n², which gives the optimal value function for all states [43], in the sense, VT" (s) sup, (s) for all h E [H] and E S. For notational simplicity, we abbreviate y=" V*. We similarly define the optimal Q-value function Q* Recall that Q* satisfies the Bellman optimality equation:
as) (Th = rn(s,a) + Eg (ss,) max Qi (s', a').
d'A
for all (s, a. h) x Ax [H). We also call To the Bellman operator at step h.
We study deterministic reward for notational simplicity. Our results readily generalize random rewards.

---

e-optimality and regret We say a policy т is e-optimal if (s1 2 Vi((s1) Suppose an agent interacts with the environment for K episodes. Denote by x² the policy the agent follows in episode & [K]. The (accumulative) regret defined as
K
Reg(As () = -v) (s1))-
The objective of reinforcement learning is to find an e-optimal policy within small number of interactions or to achieve sublinear regret.
2.1 Function approximation
In this paper, we consider reinforcement learning with value function approximation. Formally, the learner is given function class FF = candidate functions approximate Q the optimal Q-value function at step h. Since no reward is collected in the (H + 1)th steps, we always set fu+1 = O.
FH, where Fr, S (S A + [0, 1]) offers set of
Reinforcement learning with function approximation in general is extremely challenging without further assumptions (see, e.g., hardness results [16, 44]). Below, we present two assumptions about function approximation that are commonly adopted in the literature.
Assumption (Realizabilitty) Q for all h E [H].
Realizability requires the function class is well-specified, i.e., function class in fact contains the optimal Q-value function Q* with no approximation error.
Assumption (Completeness). Th.F+1 S. Fi,foor for all h E [H].
Note Th.Fk+1 is defined as (Ta/nt1: : fu+1 E Fn-1)- Completeness requires the function class F to be closed under the Bellman operator.
When function class FF has finite elements, function class F. When addressing function classes with infinite elements, we need a notion similar to cardinality. We use the standard e-covering number.
use its cardinality [F] to measure the "size" of
Definition 3 (e-covering number). The e-covering number of a set V under metric denoted as N(V,e, p). is the minimum integer n such that there exists a subset Vo C with [Vol n, and for any E V, there exists Vo such that p(z, y) S
We refer readers to standard textbooks [see, e.g., 45] for further properties of covering number. In this paper, we will always apply the covering number on function class F = Fi x ... x FH. and use metric p(f.g) g) = max, fi Iulloc. For notational simplicity, we omit the metric dependence and denote the covering number as (c))).
2.2 Eluder dimension
One class of functions highly related to this paper is the function class of low Eluder dimension [18]. Definition 4 (<-independence between points). Let G be a function class defined on X, and 2, with respect to G if there exist 91 92 9
...,,T E X. We say is c-independent of {x1, T2.......... , F.
such that ( - g2(x:))² I c, but g1(2) - g2(2)
Intuitively, 2 is independent of {æ1, x2, .., Fn means if that there exist two "certifying" functions @1 and 92. so that their function values are similar at all points { but the values are rather different This independence relation naturally induces the following complexity measure.
Definition 5 (Eluder dimension). Let G be function class defined on X. The Eluder dimension dimp <) is the length of the longest sequence {æ1, (x....., ..,,,,,, xx C. X such that there exists é' where is e' d'independent of (a1...., -i-1) for all i E [m].
Recall that vector space has dimension of elements (x1,..., such that is linearly independent of (x1,-.., for all i E [n]. Fluder dimension generalizes the linear independence relation in standard vector space to capture both nonlinear independence and approximate independence, and thus is more general.
and only if dl is the length of the longest sequence
5

---

3 Bellman Eluder Dimension
In this section, we introduce our new complexity measure-Bellmeee Eluder (BE) dimension. As one of its most important properties, we will show that the family of problems with low BE dimension contains the two existing most general tractable problem classes in RL- problems with low Bellman rank, and problems with low Eluder dimension (see Figure 1).
We start by developing Russo and Van Roy [18] (see Section 2.2 for more details).
distributional version of the original Eluder dimension proposed by
Definition 6 (e-independence between distributions). Ler 9 be a function class defined on X, and v, . Mn, be probability measures over X. We say is e-independent of {pi, ........ Pn with respect to G if there exists g E G such that VE (,, [g]]² S but [gE > E.
Definition 7 (Distributional Eluder (DE) dimension). Let G be a function class defined on X, and be a family of probability measures over X. The distributional Eluder dimension dimpDE 11, c) is the length of the longest sequence {Pi,....PP C. 11 such that there exists e' 2 e ewhere p; is e e-independent of {pI,..., for all [n].
Definition 6 and Definition generalize Definition 4 and Definition 5 to their distributional versions, by inspecting the expected values of functions instead of the function values at points, and by re- stricting the candidate distributions to certain family II. The main advantage of this generalization exactly in the statistical setting, where estimating the expected values of functions with respect to a certain distribution family can be easier than estimating function values at each point (which is the case for RL large state spaces).
is clear that the standard Fluder dimension is a special case of the distributional Eluder dimension, because if we choose dimg (G, e) = dimpE(( - G, 11, where G - G = {g1
(-) x E X3 where (.) the dirac measure centered at æ, then
91. E G}.
Now are ready to introduce the key notion in this paper-Bellman Eluder dimension.
Definition 8 (Bellman Eluder (BE) dimension). Let (1 TT.FF == [fr Thfn+1: f F} be the set of Bellman residuals induced by F at step h, and
(1I,] h- be collection of H probability measure families over S x A. The C-Bellman Eluder of F with respect to II is defined as
LimBE(FFII,
max dimpe NE(H]
II.
Remark 9 (Q-type V.S. V-type). Definition 8 is based the Bellman residuals functions that take state-action pair as input, thus referred to as Q-type BE dimension. Alternatively, one can define V- type BE dimension using different set of Bellman residual functions that depend states only (see Appendix B). We focus on Q-type in the main paper, and present the results for V-rype in Appendix B. Both variants important, and they include different sets of examples (see Appendix B, C).
In short, Bellman Eluder dimension is simply the distributional Eluder dimension on the function class of Bellman residuals, maximizing over all steps. In addition to function class F and error Bellman Eluder dimension also depends on the choice of distribution family II. For the purpose of this paper, focus the following two specific choices.
1. Dz == {Dr (.E.)) where Dr,r denotes the collection of all probability measures over S x A at the th step, which can be generated by executing the greedy policy my induced by any f F, i.e. (-)(()) argmax fn a) for all h E [H]
2. DA == (Da,n) (PA,n)ee(H) ME[H]- probability measures that put measure on a single state-action pair.
where Da, (ō(,.e) (:)s S,a E A), i.e., the collections of
We say RL problem has low BE dimension if minne dim [I, is small.
3.1 Relations with known tractable classes of RL problems
Known tractable problem classes RL include but not limited tabular MDPs, linear MDPs [7], linear quadratic regulators [9], generalized linear MDPs [6], kernel MDPs (Appendix C), reactive POMDPs [16), reactive PSRs [46, 1]. There are two existing generic tractable problem classes that jointly contain all the examples mentioned above: the set of RL problems with low Bellman rank,

---

and the set of RL problems with low Eluder dimension. However, for these two generic sets, one does not contain the other.
In this section, we will show that our new class of RI. problems with low BE dimension in fact con- tains both low Bellman rank problems and low Eluder dimension problems (see Figure 1). That is, our new problem class covers almost all existing tractable RL problems, and to our best knowledge, the most generic tractable function class far.
Relation with low Bellman rank The seminal paper by Jiang et al. [1] proposes the complexity mecaure-Belllman rank, and shows that a majority of RL examples mentioned above have low Bellman rank. They also propose hypothesis elimination based (gorithm-OLTV that learns any low Bellman rank problem within polynomial samples. Formally,
Definition 10 (Bellman rank). The Bellman rank is the minimum integer that there exists Φn. F - Rd and the F + Ed for each h E [Lt], such that for any f, F, the average Bellman error.
E(f,Tg, h) = Exy Exy. -Tff++1) an) = (fx(f), (on(f) (f)).
where [[o(())l2 (1))) S. and Ç is the normalization parameter.
We remark that similar to Bellman Eluder dimension, Bellman rank also has two variants- Q-type (Definition 10) and V-tppe (see Appendix B). Recall that we use π to denote the greedy policy induced by value function f. Intuitively, a problem with Bellman rank says its average Bellman error can be decomposed as the inner product of two d-dimensional vectors, where one vector depends on the roll-in policy r while the other vector depends on the value function f. At high level, it claims that the average Bellman error has a linear inner product structure.
Proposition 11 (low Bellman rank low BE dimension). If an MDP with function class has Bellman rank d with normalization parameter Ç, then
dimBe (F,DD, S O(1 + dllog1 + c/e)).
Proposition 11 claims that problems with low Bellman rank also have low BE dimension, with a small multiplicative factor that is only logarithmic in Ç 6-1
Relation with low Eluder dimension Wang et al. [17] study the setting where the function class FF has low Eluder dimension, which includes generalized linear functions. They prove that, when the completeness assumption is satisfied, low Eluder dimension problems can be efficiently learned in polynomial samples.
Proposition 12 (low Eluder dimension low BE dimension). Assume satisfies completeness (Assumption 2). Then for all > O,
dimBg (F.Da.c) I max (aimg(Fr,4
Proposition 12 asserts that problems with low Bluder dimension also have low BE dimension, which natural consequence of completeness and the fact that Eluder dimension is special case of distributional Eluder dimension.
Finally, we show that the set of low BE dimension problems is strictly larger than the union of low Eluder dimension problems and low Bellman rank problems.
Proposition 13 (low BE dimension df low Eluder dimension U low Bellman rank). For any N+, there exists MDP and function class F so that for all e E (0, we have LimBe(FFDD E) = dimgæ EA, < but min(minge dimg((F, e), Bellman rank] 2
In particular, the family of low BE dimension includes new examples such as kerel reactive POMDPs (Appendix C), which can not be addressed by the framework of either Bellman rank or Eluder dimension.
'[17] assume for any function g (not necessarily in F), Tg E F. which is stronger than the completeness assumption presented in this paper (Assumption 2).
7

---

Algorithm 1 GOLF(F,G, K Global Optimism based on Local Fitting
1: Initialize: Di..... Dzr <- B.
2: for episode & from 1 to K do
3: Choose policy π = gK, where f = jrggaa f(s1, Ty(s)))
4: Collect a trajectory (51, f1,,,,,.......................,. sH, ag TH, 8H+1) by following x².
5: Augment D/= = Dr. U [(sh: On, rh, 8h+1)} for all h E [H].
6: Update
B {SEF: CDu(fn fl+t1) S inf LD, fi+11) + 3 for all h [H]
gEsn
where CD, (Eh, Sh+2)= =
Σ
[En(s, a) - max (6+1(s', a'EA
(2)
(s,,,
7: Output T. sampled uniformly at random from { Jk-1
Algorithm GOLF
class of RL problems with low BE dimension, and shows that the new class is rich, containing almost all the existing known tractable RL. problems so far. In this section, propose new simple optimization-base algorithm- algorithm-Glohan Global Optimism based on Local Fitting (GOLF). We prove that, low BE dimension problems are indeed tractable, i.e., GOLF can find near- optimal policies for these problems within polynomial number of samples.
Section 3 defines
At a high level, GOLF can be viewed as an optimistic version of the classic DggrrithmFiitted Q- Iteration (FQI) [42]. GOLF generalizes the ELEANOR algorithm [8] from the special linear setting to the general setting with arbitrary function classes.
The pseudocode of GOLF is given in Algorithm 1. GOLF initializes datasets (Da) H to be empty sets, and confidence set 8 to be F. Then, in each episode, GOLF performs two main steps:
Line 3 (Optimistic planning): compute the most optimistic value function fk from the confidence set B constructed in the last episode, and choose x* to be its greedy policy.
Line 4-6 (Execute the policy and update the confidence set): execute policy n² for one episode, collect data, and update the confidence set using the new data.
At the heart of GOLF is the way we construct the confidence set Bh For each h E [H], GOLF maintains local regression constraint using the collected transition data Dr at this step
LD., (fr. f(+11) S inf LD, (g. fa+1) + 3, gEG,.
(3)
where / is confidence parameter, and LD, is the squared loss defined in (2), which can be viewed as a proxy to the squared Bellman error at step h. We remark that FQI algorithm [42] simply updates fn + argmin LDD, (Ø, fn+1). Our constraint (3) can be viewed as a relaxed version of this update, which allows fn. to be not only the minimizer of the loss LD, (- 1), but also any function whose loss is only slightly larger than the optimal loss over the auxiliary function class Gr-
We remark that in general, the optimization problem in Line 3 of GOLF not be solved computa- tionally efficiently.
4.1 Theoretical guarantees
In this subsection, we present the theoretical guarantees for GOLF, which hold under Assumption (realizability) and the following generalized completeness assumption introduced in [47, 21]. Let G = Gi x XG GH be an auxiliary function class provided to the learner where each G,, C (Sx x - [0, Generalized completeness requires the auxiliary function class G to be rich enough so that applying Bellman operator to any function in the primary function class F will end up in G.
Assumption 14 (Generalized completeness). Tr.F++1 S 9n. for all h E [H].
If we choose G = F, then Assumption 14 equivalent to the standard completeness assumption (Assumption 2). Now, we ready to present the main theorem for GOLF.
8

---

Theorem 15 (Regret of GOLF), Under Assumption 1. 14, there exists an absolute constant e such that for any 8 E (0, 1), K N, if we choose parameter 8 = clog\Nzug(L/K) KHH/6] in GOLF, then with probability at least 1 - 6, for all & E [ we have
Reg(k) =
Σ 1=1
(=) - (oD) 2 Ol1 dkB),
where d minne dimBE (F.II./VK)) is the BE dimension.
Theorem 15 asserts that, under the realizability and completeness assumptions, the general class of RL problems with low BE dimension indeed tractable: there exists an algorithm (GOLF) that can achieve VK regret, whose multiplicative factor depends only polynomially on the horizon of MDP H, the BE dimension d, and the log covering number of the two function classes. Most importantly, the regret independent of the number of the states, which is crucial for dealing with practical RL problems with function approximation, where the state spaces are typically exponentially large.
We remark that when function class F U G has finite number of elements, its covering number is upper bounded by its cardinality FF For a wide range of function classes in practice, the log e'-covering number has only logarithmic dependence number as log Nuug and omit its e' dependency for clean presentation. Theorem 15 claims that the regret scales as O( /dK log Fug)), where (.) omits absolute constants and logarithmic terms."
e'. Informally, we denote the log covering
By the standard aaline-to-batch argument, also derive the sample complexity of GOLF.
Corollary 16 (Sample Complexity of GOLF), Under Assumption 1, 2. there exists an absolute constant e such that for any E (0, 1]. if we choose 3 = clog[NFugg (e? /ddH)) HK] GOLF, then the output policy Th is O(e) (o)tomml with probability at least 1/2. if
Hdd 22
Hd
K K26 Ω
log
NFug
H2d
where d = min dimBE (F, IT, c/H) is the BE dimension.
Corollary 16 claims that O(H²d logFe)) samples are enough for GOLF to learn a near- optimal policy of any low BE dimension problem. Our sample complexity scales linear in both the BE dimension d, and the log covering number log(Nrus).
To showcase the sharpness our results, we compare them to the previous results when restricted to the corresponding settings. (1) For linear function class with ambient dimension din- have BE dimension d (chin) and log(NFug) which matches the best known result [8] up to logarithmic factors; (2) For function class with low Eluder dimension [17], our results hold under weaker completeness assumptions. Our regret scales with vlg in terms of dependency on Eluder dimension de, which improves the linear dg scaling in the regret of [17]: (3) Finally, for low Bellman rank problems, our sample complexity scales linearly with Bellman rank, which improves upon the quadratic dependence in [1]. We remark that all results mentioned above assume (approximate) realizability. All except [1] assume (approximate) completeness.
(chin). Our regret bound becomes O v K)
4.2 Key ideas
in proving Theorem 15
In this subsection, we present brief proof sketch for the regret bound of GOLF. We defer all the details to Appendix F. For simplicity, we only discuss the case of choosing Dy as the distribution family II in the definition of Bellman Eluder dimension (Definition 8). The proof for using DA as the distribution family follows from similar arguments.
Our proof strategy consists of three main steps.
Step 1:
Prove optimism. We firstly show that, with high probability, the optimal value function Q* indeed lies in the confidence set B* for all k E [K] (Lemma 40 in Appendix E. which
WWe will omit log Nruu in Ō(-) notation since for many function classes, log is not small. For instance, for d d-dimensional linear function class, log Noug Ö(d).

---

is natural consequence of martingale concentration and the properties of the confidence set we designed. Because of Q B*, the optimistic planning step (Line 3) in GOLF guarantees that (x1) I maxa J (#1, a) for every episode k. This optimism allows the following upper bound on regret
K
H
K
Reg( ()) &
Σ max of (s1, V7- (51)
Eet 1(f - -Ttt) (4)
where the right equality follows from the standard policy loss decomposition (see, c.g., Lemma in [1], and Ex denotes the expectation taken over sequence (51, di,...,, aH) when executing policy т.
Step 2: Utilize the sharpness of our confidence set. Recall that our construction of the confi- dence set Line 6 of GOLF forces f computed in episode & to have a small loss CD,, which is a proxy for empirical squared Bellman error under data Dr, Since data Dj, in episode le are collected by executing each n' for one episode for all i < k, by standard martingale concentration arguments and the completeness assumption, we can show that with high probability (Lemma 39 in Appendix 1.
1 E. [Uh - -TT--hhhhee -Tsh+1 ]m]] SO(3), for all (k, E [K] x [H].
Σ
(5)
Step 3: Establish relations between (4) and (5). So far, we want upper-bound (4), while we know (5). We note that the RHS of (4) is very similar to the LHS of (5), except that the latter is the squared Bellman error, and the expectation taken under previous policy æ' for To establish the connection between these two, it turns out that we need the Bellman Eluder dimension to be small. Concretely, we have the following lemma.
Lemma 17. Given a function class & defined on X' with [o(x)] S for all (0,x) $ x X, and a family of probability measures IT over X. Suppose sequence { C @ and {uK)k=
K C II
satisfy that for all k [K]. E
s B. Then for all k E [K], Σ [oil S
O( O(Vdinn dimppe( ④ II, 3/k)
Lemma 17 is simplification of Lemma 41 in Appendix E, which is a modification of Lemma 2 in [18]. Intuitively, Lemma 17 can be viewed as an analogue of the pigeon-hole principle for DE dimension. Choose & be the function class of Bellman residuals, and μt to be the distribution under policy n² we finish the proof.
Conclusion
In this paper, we propose a complexity measure- Bellman Eluder (BE) dimension for rein- forcement learning with function approximation. Our new complexity measure identifies a new rich class of RL problems that subsumes majority of existing tractable problem classes in RL. We de- sign a new optimization-base algorithm-GoLF GOLF, and provide a new analysis for algorithm OLIVE. Both algorithms show that the new rich class of RL problems we identified in fact can be learned within polynomial number of samples. We hope our results shed light on the future research in finding the minimal structural assumptions that allow sample-efficient reinforeement learning.
Acknowledgement
This work was partial supported by National Science Foundation Grant
10

---

References
[1] Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank pac-learnable. In International Con- ference on Machine Learning, pages 1704-1713. PMLR, 2017.
[2] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioamnis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 132.5022, 2013.
[3] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanc- tot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529
(7587):484 489, 2016.
[4] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(1 101112288-2221 2013.
[5] Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. Deep reinforcement learning for dialogue generation. arXiv preprint arXiv:1606 10X.::6606.01411,, 2016.
[6] Yining Wang, Ruosong Wang. Simon Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 1rXiv:191..04136. 2019.
[7] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137- 2143, 2020.
[8] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. arXiv preprint TxXx:2003300055: 2020.
[9] Brian DO Anderson and John B Moore. Optimal control: linear quadratic methods. Courier Corporation, 2007.
[10] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Meshahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476. PMLR, 2018.
[11] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sam- ple complexity of the linear quadratic regulator. Foundations of Computational Mathematics, pages 1-47, 2019.
[12] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
[13] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 48344,4463-48, 2002.
[14] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new algorithm. Machine learning, 2(4):285-318 1988.
[15] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. 2010.
[16] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. arXiv preprint arXiv: 1602.02222. 2016.
[17] Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learn- ing with general value function approximation. arXiv preprint arXiv:2005. 2020.
[18] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of opti- mistic exploration, In Advances Neural Information Processing Systems, pages 2256-2264, 2013.

---

[19] Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value it- eration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
[20] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9MMy))881 857, 2008
[21] Jinglin Chen and Nan Jiang. Information-theoreee considerations in batch reinforcement learn- ing. arXiv preprint arXiv: (rXiv:/905.003000 2019.
[22] Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. arXiv preprint arXiv:2008. 04990, 2020.
[23] Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning, Journal of Machine Learning R 3(Oct):213-231, 2002.
[24] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[25] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. In Advances in Neural Information Processing Systems, pages 2818-2822 2015.
[26] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances Neural Information Processing Systems, pages 1184- 1 1194, 2017.
[27] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. arXiv preprint arXiv:1003.05449 2017.
[28] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds rein- forcement learning without domain knowledge using value function bounds. arXiv preprint arXiv:1901.00210, 2019.
[29] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages
2018.
[30] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learn- ing via reference-advantage decomposition. arXiv preprint arXiv:2004. 10019, 2020.
[31] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learn- ing Theory, pages 578-598. PMLR, 2021.
[32] Qi Cai,, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy 2019.
optimization. arXiv preprint
[33] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably ef- ficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33, 2020.
[34] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances Neural Information Processing Systems, 33, 2020.
[35] Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning, Advances in Neural Information Processing Systems, 33, 2020.
[36] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model- based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898-2933, 2019.
[37] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder di- mension. In Advances in Neural Information Processing Systems, pages 1466-1477 1474, 2014.
12

---

[38] Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Root-n-regret for learning in markov de- cision processes with function approximation and low bellman rank. In Conference on Learn- ing Theory, pages 1554-1557 PMLR, 2020.
[39] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang. and Michael I Jordan. Bridging explo- ration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations. arXiv preprint arXiv:2011.0422) 2020.
[40] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependen complexity of contextual bandits and reinforcement learning: A disagreement-based perspec- tive. arXiv preprint arXiv:2010.03104, 2020.
[41] Simon Du, Sham M Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103.10892 2021.
[42] Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning, 4(1):1-103, 2010.
[43] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[44] Gellert Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. arXiv preprint arXiv:2010.01374. 2020.
[45] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[46] Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv: 12Xi::1207.4167 2012.
[47] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with hellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, (1(1):19111))))11 129, 2008
[48] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac rl with rich observations. In Advances in neu- ral information processing systems, pages 1422-1432, 2018.
[49] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646, 2014.
13


Reviews:
[{"review_id": "tLbj5gWB4qV", "reviewer": "Reviewer_S8yr", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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})$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "lKAxT2eZnfg", "reviewer": "Reviewer_TbTF", "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nTechnically, 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. \n\nOverall, this is a great paper. It's pretty clear that it should be accepted. I will fight for its acceptance. \n\nComments\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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]. \n\n[1] Efficient exploration and value function generalization in deterministic systems\n\n[2] Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle\n\n[3] Agnostic Q-learning with Function Approximation in Deterministic Systems: Near-Optimal Bounds on Approximation Error and Sample Complexity\n\n[4] On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "OENE8-6AyR", "reviewer": "Reviewer_T8on", "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. \n\nThey 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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I support accepting the paper. However, I have a few concerns and would be open to increase my score depending on the feedback: \n\n(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? \n\n(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? \n\n(3.) Can GOLF be implemented efficiently for any RL setting? What about tabular RL? \n\n(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? \n\n(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. \n\n(6.) Can we compare the BE dimension with the distribution class D_{F} and D_{\\Delta}. Is one always larger than the other?  \n\nThe paper is very well written. Minor typo: Line 338: discusses -> discuss. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8-10 hours"}, "extra_text": {}}, {"review_id": "Kl-4NJKREOu", "reviewer": "Reviewer_bYxF", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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:\n\n1. About the BE dimension\n\nIn 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:\n\nThe 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). \n\nWhat I find interesting/important is that BE covers more. In Proposition 13, the example illustrates two things:\n\na) 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. \n\nb) 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.\n\nDo you have any intuitive explanation on how BE covers more than bellman rank and eluder except for the freedom of selecting distributions?  \n\n2. About the benefit of BE.\n\nWhat 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.\n\n3. Strong condition on distributions. \n\nBoth D_F and D_\\Delta contain possibly numerous distributions. I wonder if there is any idea on how to shrink the distribution set?\n\nMinors:\n1. At Line 221, an RL problem, not a.\n2. 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))?\n3. At line 217, should there be no comma in front of which?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

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)