Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

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 eliminationbased algorithm—OLIVE [proposed in 1]. 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.

heading: 1 Introduction
text: Modern Reinforcement Learning (RL) commonly engages practical problems with an enormous number of states, where function approximation must be deployed to approximate the true value function using functions from a prespecified function class. Function approximation, especially based on deep neural networks, lies at the heart of 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 a new series of theoretical challenges when comparing to the classic tabular RL: (1) generalization, to generalize knowledge from the visited states to the unvisited states due to the enormous state space. (2) limited expressiveness, 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, to address the tradeoff between exploration and exploitation when above challenges are present.
Consequently, most existing theoretical results on efficient RL with function approximation rely on 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 (NeurIPS 2021).
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-efficient algorithms that provably learn any RL problem in this class.
The attempts to find weak or minimal structural assumptions that allow statistical learning can be traced in supervised learning where VC dimension [12] or Rademacher complexity [13] is proposed, or in online learning where Littlestone dimension [14] or 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 in this direction. To begin with, Jiang et al. [1] introduces a generic complexity notion—Bellman rank, which can be proved small for many RL problems including linear MDPs [7], reactive POMDPs [16], etc. [1] further propose an hypothesis elimination-based algorithm— OLIVE for sample-efficient 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 a 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 a new complexity measure for RL—Bellman Eluder (BE) dimension. We prove that the family of RL problems of 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 new problems such as kernel reactive POMDPs (see Appendix C) which were not known to be sample-efficiently learnable.
• We design a new optimization-based algorithm—GOLF, which provably learns nearoptimal 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 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.
• We reanalyze the hypothesis elimination based algorithm—OLIVE proposed in [1]. We show it can also learn RL problems with low BE dimension sample-efficiently, under slightly weaker assumptions but with worse sample complexity comparing to GOLF.

heading: 1.1 Related works
text: This section reviews prior theoretical works on RL, under Markov Decision Process (MDP) models.
1The 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 B for more details.
We remark that there has been a 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. In 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–30]. In the episodic setting with non-stationary dynamics, the best regret bound Õ( √ H2|S||A|T ) is achieved by both model-based [27] and modelfree [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-theoretically 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 Õ(d √ 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 et al. [1] propose a 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 completeness assumption, but provides sharper sample complexity guarantee.
Wang et al. [17] propose a UCB-type algorithm with a regret guarantee under the assumption that the function class has a low eluder dimension. Again, we will show that low Eluder dimension is a 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 Concurrent to this work, Du et al. [41] propose a new general tractable class of RL problems—bilinear class with low effective dimension (also known as low critical information gain in Du et al. [41]). We comment on the similarities and differences between two works as follows.
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 approximation—GOLF, a natural and clean algorithm which can be viewed as an optimistic version of classical algorithm—Fitted Q-Iteration [42]. GOLF gives much sharper sample complexity guarantees compared to [41] for various settings, and is minimaxoptimal when applied to the linear setting [8].
In terms of richness of new classes identified, it depends on (a) what structure of MDP the complexity 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] including low occupancy complexity, linear Q?/V ?, Q? state aggregation, feature selection/FLAMBE.
Nevertheless, our work can not address examples with model-based function approximation (e.g., low witness rank [36]) while [41] can. On the other hand, Du et 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 d 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 Ω̃(d2).

heading: 1.2 Paper organization
text: We present preliminaries in Section 2, the definition of Bellman-Eluder 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 be provided in Appendix B and C. All the proofs are postponed to the appendix.

heading: 2 Preliminaries
text: We consider episodic Markov Decision Process (MDP), denoted byM = (S,A, H,P, r), where S is the state space, A is the action space, H is the number of steps in each episode, P = {Ph}h∈[H] is the collection of transition measures with Ph(s′ | s, a) equal to the probability of transiting to s′ after taking action a at state s at the hth step, and r = {rh}h∈[H] is the collection of reward functions with rh(s, a) equal to the deterministic reward received after taking action a at state s at the hth step. 2 Throughout this paper, we assume reward is non-negative, and ∑H h=1 rh(sh, ah) ≤ 1 for all possible sequence (s1, a1, . . . , sH , aH).
In each episode, the agent starts at a fixed initial state s1. Then, at each step h ∈ [H], the agent observes its current state sh, takes action ah, receives reward rh(sh, ah), and causes the environment to transit to sh+1 ∼ Ph(· | sh, ah). Without loss of generality, we assume there is a terminating state send which the environment will always transit to at step H + 1, and the episode terminates when send is reached.
Policy and value functions A (deterministic) policy π is a collection of H functions {πh : S → A}Hh=1. We denote V πh : S → R as the value function at step h for policy π, so that V πh (s) gives the expected sum of the remaining rewards received under policy π, starting from sh = s, till the end of the episode. In symbol,
V πh (s) := Eπ[ H∑
h′=h
rh′(sh′ , ah′) | sh = s].
Similarly, we denote Qπh : S ×A → R as the Q-value function at step h for policy π, where
Qπh(s, a) := Eπ[ H∑
h′=h
rh′(sh′ , ah′) | sh = s, ah = a].
There exists an optimal policy π?, which gives the optimal value function for all states [43], in the sense, V π ?
h (s) = supπ V π h (s) for all h ∈ [H] and s ∈ S . For notational simplicity, we abbreviate
V π ?
as V ?. We similarly define the optimal Q-value function as Q?. Recall that Q? satisfies the Bellman optimality equation:
Q?h(s, a) = (ThQ?h+1)(s, a) := rh(s, a) + Es′∼Ph(·|s,a) max a′∈A Q?h+1(s ′, a′). (1)
for all (s, a, h) ∈ S ×A× [H]. We also call Th the Bellman operator at step h.
2We study deterministic reward for notational simplicity. Our results readily generalize to random rewards.
-optimality and regret We say a policy π is -optimal if V π1 (s1) ≥ V ?1 (s1) − . Suppose an agent interacts with the environment for K episodes. Denote by πk the policy the agent follows in episode k ∈ [K]. The (accumulative) regret is defined as
Reg(K) := K∑ k=1 [V ?1 (s1)− V π k 1 (s1)].
The objective of reinforcement learning is to find an -optimal policy within a small number of interactions or to achieve sublinear regret.

heading: 2.1 Function approximation
text: In this paper, we consider reinforcement learning with value function approximation. Formally, the learner is given a function class F = F1 × · · · × FH , where Fh ⊆ (S ×A → [0, 1]) offers a set of candidate functions to approximate Q?h—the optimal Q-value function at step h. Since no reward is collected in the (H + 1)th steps, we always set fH+1 = 0.
Reinforcement learning with function approximation in general is extremely challenging without further assumptions (see, e.g., hardness results in [16, 44]). Below, we present two assumptions about function approximation that are commonly adopted in the literature. Assumption 1 (Realizability). Q?h ∈ Fh for all h ∈ [H].
Realizability requires the function class is well-specified, i.e., function class F in fact contains the optimal Q-value function Q? with no approximation error. Assumption 2 (Completeness). ThFh+1 ⊆ Fh for all h ∈ [H].
Note ThFh+1 is defined as {Thfh+1 : fh+1 ∈ Fh+1}. Completeness requires the function class F to be closed under the Bellman operator.
When function class F has finite elements, we can use its cardinality |F| to measure the “size” of function class F . When addressing function classes with infinite elements, we need a notion similar to cardinality. We use the standard -covering number. Definition 3 ( -covering number). The -covering number of a set V under metric ρ, denoted as N (V, , ρ), is the minimum integer n such that there exists a subset Vo ⊂ V with |Vo| = n, and for any x ∈ V , there exists y ∈ Vo such that ρ(x, y) ≤ .
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 = F1 × · · · × FH , and use metric ρ(f, g) = maxh ‖fh − gh‖∞. For notational simplicity, we omit the metric dependence and denote the covering number as NF ( ).

heading: 2.2 Eluder dimension
text: 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 z,x1, x2 ,. . .,xn∈ X . We say z is -independent of {x1, x2, . . . , xn} with respect to G if there exist g1, g2 ∈ G such that √∑n i=1(g1(xi)− g2(xi))2 ≤ , but g1(z)− g2(z) > .
Intuitively, z is independent of {x1, x2, . . . , xn} means if that there exist two “certifying” functions g1 and g2, so that their function values are similar at all points {xi}ni=1, but the values are rather different at z. This independence relation naturally induces the following complexity measure. Definition 5 (Eluder dimension). Let G be a function class defined on X . The Eluder dimension dimE(G, ) is the length of the longest sequence {x1, . . . , xn} ⊂ X such that there exists ′ ≥ where xi is ′-independent of {x1, . . . , xi−1} for all i ∈ [n].
Recall that a vector space has dimension d if and only if d is the length of the longest sequence of elements {x1, . . . , xd} such that xi is linearly independent of {x1, . . . , xi−1} for all i ∈ [n]. Eluder dimension generalizes the linear independence relation in standard vector space to capture both nonlinear independence and approximate independence, and thus is more general.

heading: 3 Bellman Eluder Dimension
text: In this section, we introduce our new complexity measure—Bellman 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 a new distributional version of the original Eluder dimension proposed by Russo and Van Roy [18] (see Section 2.2 for more details). Definition 6 ( -independence between distributions). Let G be a function class defined on X , and ν, µ1, . . . , µn be probability measures over X . We say ν is -independent of {µ1, µ2, . . . , µn} with respect to G if there exists g ∈ G such that √∑n i=1(Eµi [g])2 ≤ , but |Eν [g]| > . 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 dimDE(G,Π, ) is the length of the longest sequence {ρ1, . . . , ρn} ⊂ Π such that there exists ′ ≥ where ρi is ′-independent of {ρ1, . . . , ρi−1} for all i ∈ [n].
Definition 6 and Definition 7 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 restricting the candidate distributions to a certain family Π. The main advantage of this generalization is 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 in large state spaces).
It is clear that the standard Eluder dimension is a special case of the distributional Eluder dimension, because if we choose Π = {δx(·) | x ∈ X} where δx(·) is the dirac measure centered at x, then dimE(G, ) = dimDE(G − G,Π, ) where G − G = {g1 − g2 : g1, g2 ∈ G}. Now we are ready to introduce the key notion in this paper—Bellman Eluder dimension. Definition 8 (Bellman Eluder (BE) dimension). Let (I − Th)F := {fh − Thfh+1 : f ∈ F} be the set of Bellman residuals induced by F at step h, and Π = {Πh}Hh=1 be a collection of H probability measure families over S ×A. The -Bellman Eluder of F with respect to Π is defined as
dimBE(F ,Π, ) := max h∈[H]
dimDE ( (I − Th)F ,Πh, ) .
Remark 9 (Q-type v.s. V-type). Definition 8 is based on the Bellman residuals functions that take a state-action pair as input, thus referred to as Q-type BE dimension. Alternatively, one can define Vtype BE dimension using a different set of Bellman residual functions that depend on states only (see Appendix B). We focus on Q-type in the main paper, and present the results for V-type in Appendix B. Both variants are 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 Π. For the purpose of this paper, we focus on the following two specific choices.
1. DF := {DF,h}h∈[H], where DF,h denotes the collection of all probability measures over S × A at the hth step, which can be generated by executing the greedy policy πf induced by any f ∈ F , i.e., πf,h(·) = argmaxa∈A fh(·, a) for all h ∈ [H].
2. D∆ := {D∆,h}h∈[H], where D∆,h = {δ(s,a)(·)|s ∈ S, a ∈ A}, i.e., the collections of probability measures that put measure 1 on a single state-action pair.
We say a RL problem has low BE dimension if minΠ∈{DF ,D∆} dimBE(F ,Π, ) is small.

heading: 3.1 Relations with known tractable classes of RL problems
text: Known tractable problem classes in RL include but not limited to 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 RL problems with low BE dimension in fact contains 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, is the most generic tractable function class so far.
Relation with low Bellman rank The seminal paper by Jiang et al. [1] proposes the complexity measure—Bellman rank, and shows that a majority of RL examples mentioned above have low Bellman rank. They also propose a hypothesis elimination based algorithm—OLIVE, that learns any low Bellman rank problem within polynomial samples. Formally,
Definition 10 (Bellman rank). The Bellman rank is the minimum integer d so that there exists φh : F → Rd and ψh : F → Rd for each h ∈ [H], such that for any f, f ′ ∈ F , the average Bellman error.
E(f, πf ′ , h) := Eπf′ [(fh − Thfh+1)(sh, ah)] = 〈φh(f), ψh(f ′)〉,
where ‖φh(f)‖2 · ‖ψh(f ′)‖2 ≤ ζ, 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-type (see Appendix B). Recall that we use πf 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 πf ′ , while the other vector depends on the value function f . At a 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 F has Bellman rank d with normalization parameter ζ, then
dimBE(F ,DF , ) ≤ O(1 + d log(1 + ζ/ )).
Proposition 11 claims that problems with low Bellman rank also have low BE dimension, with a small multiplicative factor that is only logarithmic in ζ and −1.
Relation with low Eluder dimension Wang et al. [17] study the setting where the function class F has low Eluder dimension, which includes generalized linear functions. They prove that, when the completeness assumption is satisfied,3 low Eluder dimension problems can be efficiently learned in polynomial samples.
Proposition 12 (low Eluder dimension ⊂ low BE dimension). Assume F satisfies completeness (Assumption 2). Then for all > 0,
dimBE ( F ,D∆, ) ≤ max h∈[H] dimE(Fh, ).
Proposition 12 asserts that problems with low Eluder dimension also have low BE dimension, which is a natural consequence of completeness and the fact that Eluder dimension is a 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 6⊂ low Eluder dimension ∪ low Bellman rank). For any m ∈ N+, there exists an MDP and a function class F so that for all ∈ (0, 1], we have dimBE(F ,DF , ) = dimBE(F ,D∆, ) ≤ 5, but min{minh∈[H] dimE(Fh, ),Bellman rank} ≥ m.
In particular, the family of low BE dimension includes new examples such as kernel reactive POMDPs (Appendix C), which can not be addressed by the framework of either Bellman rank or Eluder dimension.
3[17] assume for any function g (not necessarily in F), T g ∈ F , which is stronger than the completeness assumption presented in this paper (Assumption 2).
Algorithm 1 GOLF(F ,G,K, β) — Global Optimism based on Local Fitting 1: Initialize: D1, . . . ,DH ← ∅, B0 ← F . 2: for episode k from 1 to K do 3: Choose policy πk = πfk , where fk = argmaxf∈Bk−1 f(s1, πf (s1)). 4: Collect a trajectory (s1, a1, r1, . . . , sH , aH , rH , sH+1) by following πk. 5: Augment Dh = Dh ∪ {(sh, ah, rh, sh+1)} for all h ∈ [H]. 6: Update
Bk = { f ∈ F : LDh(fh, fh+1) ≤ inf
g∈Gh LDh(g, fh+1) + β for all h ∈ [H]
} ,
where LDh(ξh, ζh+1) = ∑
(s,a,r,s′)∈Dh
[ξh(s, a)− r −max a′∈A ζh+1(s ′, a′)]2. (2)
7: Output πout sampled uniformly at random from {πk}Kk=1.

heading: 4 Algorithm GOLF
text: Section 3 defines a new 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, we propose a new simple optimization-based algorithm—Global Optimism based on Local Fitting (GOLF). We prove that, low BE dimension problems are indeed tractable, i.e., GOLF can find nearoptimal policies for these problems within a polynomial number of samples.
At a high level, GOLF can be viewed as an optimistic version of the classic algorithm—Fitted QIteration (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 {Dh}Hh=1 to be empty sets, and confidence set B0 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 Bk−1 constructed in the last episode , and choose πk to be its greedy policy.
• Line 4-6 (Execute the policy and update the confidence set): execute policy πk 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 Bk. For each h ∈ [H], GOLF maintains a local regression constraint using the collected transition data Dh at this step
LDh(fh, fh+1) ≤ inf g∈Gh LDh(g, fh+1) + β, (3)
where β is a confidence parameter, and LDh 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 fh ← argminφ∈Fh LDh(φ, fh+1). Our constraint (3) can be viewed as a relaxed version of this update, which allows fh to be not only the minimizer of the loss LDh(·, fh+1), but also any function whose loss is only slightly larger than the optimal loss over the auxiliary function class Gh. We remark that in general, the optimization problem in Line 3 of GOLF can not be solved computationally efficiently.

heading: 4.1 Theoretical guarantees
text: In this subsection, we present the theoretical guarantees for GOLF, which hold under Assumption 1 (realizability) and the following generalized completeness assumption introduced in [47, 21]. Let G = G1×· · ·×GH be an auxiliary function class provided to the learner where each Gh ⊆ (S×A → [0, 1]). 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). ThFh+1 ⊆ Gh for all h ∈ [H].
If we choose G = F , then Assumption 14 is equivalent to the standard completeness assumption (Assumption 2). Now, we are ready to present the main theorem for GOLF.
Theorem 15 (Regret of GOLF). Under Assumption 1, 14, there exists an absolute constant c such that for any δ ∈ (0, 1], K ∈ N, if we choose parameter β = c log[NF∪G(1/K) ·KH/δ] in GOLF, then with probability at least 1− δ, for all k ∈ [K], we have
Reg(k) = k∑ t=1 [ V ?1 (s1)− V π t 1 (s1) ] ≤ O(H √ dkβ),
where d = minΠ∈{D∆,DF} dimBE ( F ,Π, 1/ √ K ) is the BE dimension.
Theorem 15 asserts that, under the realizability and completeness assumptions, the general class of RL problems with low BE dimension is indeed tractable: there exists an algorithm (GOLF) that can achieve √ K 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 is 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 ∪ G has finite number of elements, its covering number is upper bounded by its cardinality |F ∪ G|. For a wide range of function classes in practice, the log ′-covering number has only logarithmic dependence on ′. Informally, we denote the log covering number as logNF∪G and omit its ′ dependency for clean presentation. Theorem 15 claims that the regret scales as Õ(H √ dK logNF∪G), where Õ(·) omits absolute constants and logarithmic terms.4
By the standard online-to-batch argument, we also derive the sample complexity of GOLF. Corollary 16 (Sample Complexity of GOLF). Under Assumption 1, 2, there exists an absolute constant c such that for any ∈ (0, 1], if we choose β = c log[NF∪G( 2/(dH2)) ·HK] in GOLF, then the output policy πout is O( )-optimal with probability at least 1/2, if
K ≥ Ω ( H2d
2 · log
[ NF∪G ( 2
H2d
) · Hd ]) ,
where d = minΠ∈{D∆,DF} dimBE ( F ,Π, /H ) is the BE dimension.
Corollary 16 claims that Õ(H2d log(NF∪G)/ 2) samples are enough for GOLF to learn a nearoptimal policy of any low BE dimension problem. Our sample complexity scales linear in both the BE dimension d, and the log covering number log(NF∪G). To showcase the sharpness of our results, we compare them to the previous results when restricted to the corresponding settings. (1) For linear function class with ambient dimension dlin, we have BE dimension d = Õ(dlin) and log(NF∪G) = Õ(dlin). Our regret bound becomes Õ(Hdlin √ K) 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 √ dE in terms of dependency on Eluder dimension dE, which improves the linear dE 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.

heading: 4.2 Key ideas in proving Theorem 15
text: In this subsection, we present a brief proof sketch for the regret bound of GOLF. We defer all the details to Appendix E. For simplicity, we only discuss the case of choosing DF as the distribution family Π in the definition of Bellman Eluder dimension (Definition 8). The proof for using D∆ 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 Bk for all k ∈ [K] (Lemma 40 in Appendix E.1), which
4We will not omit logNF∪G in Õ(·) notation since for many function classes, logNF∪G is not small. For instance, for a d̃-dimensional linear function class, logNF∪G = Õ(d̃).
is a natural consequence of martingale concentration and the properties of the confidence set we designed. Because of Q? ∈ Bk, the optimistic planning step (Line 3) in GOLF guarantees that V ?1 (s1) ≤ maxa fk1 (s1, a) for every episode k. This optimism allows the following upper bound on regret
Reg(K) ≤ K∑ k=1 ( max a fk1 (s1, a)− V π k 1 (s1) ) = H∑ h=1 K∑ k=1 Eπk [ (fkh − T fkh+1)(sh, ah) ] , (4)
where the right equality follows from the standard policy loss decomposition (see, e.g., Lemma 1 in [1]), and Eπ denotes the expectation taken over sequence (s1, a1, . . . , sH , aH) when executing policy π.
Step 2: Utilize the sharpness of our confidence set. Recall that our construction of the confidence set in Line 6 of GOLF forces fk computed in episode k to have a small loss LDh , which is a proxy for empirical squared Bellman error under data Dh. Since data Dh in episode k are collected by executing each πi 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 E.1) k−1∑
i=1
Eπi [ (fkh − T fkh+1)(sh, ah) ]2≤O(β), for all (k, h) ∈ [K]× [H]. (5) Step 3: Establish relations between (4) and (5). So far, we want to 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 is taken under previous policy πi for i < k. 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 |φ(x)| ≤ 1 for all (φ, x) ∈ Φ × X , and a family of probability measures Π over X . Suppose sequence {φk}Kk=1 ⊂ Φ and {µk}Kk=1 ⊂ Π satisfy that for all k ∈ [K], ∑k−1 i=1 (Eµi [φk])2 ≤ β. Then for all k ∈ [K], ∑k i=1 |Eµi [φi]| ≤
O( √
dimDE(Φ,Π, 1/k)βk).
Lemma 17 is a 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 Φ to be the function class of Bellman residuals, and µk to be the distribution under policy πk, we finish the proof.

heading: 5 Conclusion
text: In this paper, we propose a new complexity measure—Bellman Eluder (BE) dimension for reinforcement learning with function approximation. Our new complexity measure identifies a new rich class of RL problems that subsumes a majority of existing tractable problem classes in RL. We design a new optimization-based algorithm—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 a polynomial number of samples. We hope our results shed light on the future research in finding the minimal structural assumptions that allow sample-efficient reinforcement learning.

heading: Acknowledgement
text: This work was partial supported by National Science Foundation Grant NSF-IIS-2107304.

Review summaries:
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. 

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. 

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.