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

Introduction

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 (Mnih et al., 2013), Go (Silver et al., 2016), robotics (Kober et al., 2013), and dialogue systems (Li et al., 2016).

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 (Wang et al., 2019; Jin et al., 2020; Zanette et al., 2020a), or that the model is precisely Linear Quadratic Regulator (LQR) (Anderson and Moore, 2007; Fazel et al., 2018; Dean et al., 2019). Most of these structural assumptions rarely hold in practical applications. This naturally leads to one of the most fundamental questions in RL.

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 (Vapnik, 2013) or Rademacher complexity (Bartlett and Mendelson, 2002) is proposed, or in online learning where Littlestone dimension (Littlestone, 1988) or sequential Rademacher complexity (Rakhlin et al., 2010) 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. (2017) introduces a generic complexity notion—Bellman rank, which can be proved small for many RL problems including linear MDPs (Jin et al., 2020), reactive POMDPs (Krishnamurthy et al., 2016), etc. Jiang et al. (2017) 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. (2020) considers general function approximation with low Eluder dimension (Russo and Van Roy, 2013), and designs a UCB-style algorithm with regret guarantee. Noticeably, generalized linear MDPs (Wang et al., 2019) and kernel MDPs (see Appendix B) 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 2). The family of low BE dimension further includes new problems such as kernel reactive POMDPs (see Appendix B) which were not known to be sample-efficiently learnable.

We design a new optimization-based algorithm—Golf, which provably learns 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 or sample complexity guarantees match Zanette et al. (2020a) which is minimax optimal when specified to the linear setting. Our rates further improve upon Jiang et al. (2017); Wang et al. (2020) in low Bellman rank and low Eluder dimension settings, respectively.

We reanalyze the hypothesis elimination based algorithm—Olive proposed in Jiang et al. (2017). 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.

This section reviews prior theoretical works on RL, under Markov Decision Process (MDP) models.

We remark that there has been a long line of research on function approximation in the batch RL setting (see, e.g., Szepesvári and Munos, 2005; Munos and Szepesvári, 2008; Chen and Jiang, 2019; Xie and Jiang, 2020). 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.

Beyond the linear setting, there is a flurry line of research studying RL with general function approximation (see, e.g., Osband and Van Roy, 2014; Jiang et al., 2017; Sun et al., 2019; Dong et al., 2020; Wang et al., 2020; Yang et al., 2020; Foster et al., 2020). Among them, Jiang et al. (2017) and Wang et al. (2020) are the closest to our work.

Jiang et al. (2017) 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 Jiang et al. (2017). Our result for Golf requires an additional completeness assumption, but provides sharper sample complexity guarantee.

Wang et al. (2020) 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 Wang et al. (2020), our algorithm Golf works under a weaker completeness assumption, with a better regret guarantee.

Concurrent to this work, Du et al. (2021) 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. (2021)). 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. (2021) are based on Olive originally proposed in Jiang et al. (2017). 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 (Szepesvári, 2010). Golf gives much sharper sample complexity guarantees compared to Du et al. (2021) for various settings, and is minimax-optimal when applied to the linear setting (Zanette et al., 2020a).

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. (2021) uses effective dimension. It can be shown that low effective dimension always implies low Eluder dimension (see Appendix B.2). In short, Du et al. (2021) is more general in (a), while our work is more general in (b). As a result, neither work fully captures the other.

Preliminaries

There exists an optimal policy $\pi^{\star}$, which gives the optimal value function for all states (Puterman, 2014), in the sense, $V^{\pi^{\star}}_{h}(s)=\sup_{\pi}V^{\pi}_{h}(s)$ for all $h\in[H]$ and $s\in\mathcal{S}$. For notational simplicity, we abbreviate $V^{\pi^{\star}}$ as $V^{\star}$. We similarly define the optimal $Q$-value function as $Q^{\star}$. Recall that $Q^{\star}$ satisfies the Bellman optimality equation:

for all $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$. We also call $\mathcal{T}_{h}$ the Bellman operator at step $h$.

We say a policy $\pi$ is $\epsilon$-optimal if $V^{\pi}_{1}(s_{1})\geq V^{\star}_{1}(s_{1})-\epsilon$. Suppose an agent interacts with the environment for $K$ episodes. Denote by $\pi^{k}$ the policy the agent follows in episode $k\in[K]$. The (accumulative) regret is defined as

The objective of reinforcement learning is to find an $\epsilon$-optimal policy within a small number of interactions or to achieve sublinear regret.

1 Function approximation

In this paper, we consider reinforcement learning with value function approximation. Formally, the learner is given a function class $\mathcal{F}=\mathcal{F}_{1}\times\cdots\times\mathcal{F}_{H}$, where $\mathcal{F}_{h}\subseteq(\mathcal{S}\times\mathcal{A}\rightarrow)$ offers a set of candidate functions to approximate $Q^{\star}_{h}$—the optimal $Q$-value function at step $h$. Since no reward is collected in the $(H+1)^{\text{th}}$ steps, we always set $f_{H+1}=0$.

Reinforcement learning with function approximation in general is extremely challenging without further assumptions (see, e.g., hardness results in Krishnamurthy et al. (2016); Weisz et al. (2020)). Below, we present two assumptions about function approximation that are commonly adopted in the literature.

$Q^{\star}_{h}\in\mathcal{F}_{h}$ for all $h\in[H]$.

Realizability requires the function class is well-specified, i.e., function class $\mathcal{F}$ in fact contains the optimal $Q$-value function $Q^{\star}$ with no approximation error.

$\mathcal{T}_{h}\mathcal{F}_{h+1}\subseteq\mathcal{F}_{h}$ for all $h\in[H]$.

Note $\mathcal{T}_{h}\mathcal{F}_{h+1}$ is defined as $\{\mathcal{T}_{h}f_{h+1}:f_{h+1}\in\mathcal{F}_{h+1}\}$. Completeness requires the function class $\mathcal{F}$ to be closed under the Bellman operator.

When function class $\mathcal{F}$ has finite elements, we can use its cardinality $|\mathcal{F}|$ to measure the “size” of function class $\mathcal{F}$. When addressing function classes with infinite elements, we need a notion similar to cardinality. We use the standard $\epsilon$-covering number.

The $\epsilon$-covering number of a set $\mathcal{V}$ under metric $\rho$, denoted as $\mathcal{N}(\mathcal{V},\epsilon,\rho)$, is the minimum integer $n$ such that there exists a subset $\mathcal{V}_{o}\subset\mathcal{V}$ with $|\mathcal{V}_{o}|=n$, and for any $x\in\mathcal{V}$, there exists $y\in\mathcal{V}_{o}$ such that $\rho(x,y)\leq\epsilon$.

We refer readers to standard textbooks (see, e.g., Wainwright, 2019) for further properties of covering number. In this paper, we will always apply the covering number on function class $\mathcal{F}=\mathcal{F}_{1}\times\cdots\times\mathcal{F}_{H}$, and use metric $\rho(f,g)=\max_{h}\|f_{h}-g_{h}\|_{\infty}$. For notational simplicity, we omit the metric dependence and denote the covering number as $\mathcal{N}_{\mathcal{F}}(\epsilon)$.

2 Eluder dimension

One class of functions highly related to this paper is the function class of low Eluder dimension (Russo and Van Roy, 2013).

Let $\mathcal{G}$ be a function class defined on $\mathcal{X}$, and $z$,$x_{1},x_{2}$ ,$\ldots$,$x_{n}$$\in\mathcal{X}$. We say $z$ is $\epsilon$-independent of $\{x_{1},x_{2},\ldots,x_{n}\}$ with respect to $\mathcal{G}$ if there exist $g_{1},g_{2}\in\mathcal{G}$ such that $\sqrt{\sum_{i=1}^{n}(g_{1}(x_{i})-g_{2}(x_{i}))^{2}}\leq\epsilon$, but $g_{1}(z)-g_{2}(z)>\epsilon$.

Intuitively, $z$ is independent of $\{x_{1},x_{2},\ldots,x_{n}\}$ means if that there exist two “certifying” functions $g_{1}$ and $g_{2}$, so that their function values are similar at all points $\{x_{i}\}_{i=1}^{n}$, but the values are rather different at $z$. This independence relation naturally induces the following complexity measure.

Recall that a vector space has dimension $d$ if and only if $d$ is the length of the longest sequence of elements $\{x_{1},\ldots,x_{d}\}$ such that $x_{i}$ is linearly independent of $\{x_{1},\ldots,x_{i-1}\}$ for all $i\in[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.

Bellman Eluder Dimension

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 2).

We start by developing a new distributional version of the original Eluder dimension proposed by Russo and Van Roy (2013) (see Section 2.2 for more details).

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 $\Pi$. 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).

Now we are ready to introduce the key notion in this paper—Bellman Eluder dimension.

Let $(I-\mathcal{T}_{h})\mathcal{F}:=\{f_{h}-\mathcal{T}_{h}f_{h+1}:\ f\in\mathcal{F}\}$ be the set of Bellman residuals induced by $\mathcal{F}$ at step $h$, and $\Pi=\{\Pi_{h}\}_{h=1}^{H}$ be a collection of $H$ probability measure families over $\mathcal{S}\times\mathcal{A}$. The $\epsilon$-Bellman Eluder of $\mathcal{F}$ with respect to $\Pi$ is defined as

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 V-type BE dimension using a different set of Bellman residual functions that depend on states only (see Appendix A). We focus on Q-type in the main paper, and present the results for V-type in Appendix A. Both variants are important, and they include different sets of examples (see Appendix A, B).

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 $\mathcal{F}$ and error $\epsilon$, Bellman Eluder dimension also depends on the choice of distribution family $\Pi$. For the purpose of this paper, we focus on the following two specific choices.

$\mathcal{D}_{\Delta}:=\{\mathcal{D}_{\Delta,h}\}_{h\in[H]}$, where $\mathcal{D}_{\Delta,h}=\{\delta_{(s,a)}(\cdot)|s\in\mathcal{S},a\in\mathcal{A}\}$, i.e., the collections of probability measures that put measure $1$ on a single state-action pair.

Known tractable problem classes in RL include but not limited to tabular MDPs, linear MDPs (Jin et al., 2020), linear quadratic regulators (Anderson and Moore, 2007), generalized linear MDPs (Wang et al., 2019), kernel MDPs (Appendix B), reactive POMDPs (Krishnamurthy et al., 2016), reactive PSRs (Singh et al., 2012; Jiang et al., 2017). 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 2). 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.

The seminal paper by Jiang et al. (2017) 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,

where $\|\phi_{h}(f)\|_{2}\cdot\|\psi_{h}(f^{\prime})\|_{2}\leq\zeta$, and $\zeta$ 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 A). Recall that we use $\pi_{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 $\pi_{f^{\prime}}$, 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.

If an MDP with function class $\mathcal{F}$ has Bellman rank $d$ with normalization parameter $\zeta$, then

Proposition 11 claims that problems with low Bellman rank also have low BE dimension, with a small multiplicative factor that is only logarithmic in $\zeta$ and $\epsilon^{-1}$.

Wang et al. (2020) study the setting where the function class $\mathcal{F}$ has low Eluder dimension, which includes generalized linear functions. They prove that, when the completeness assumption is satisfied,Wang et al. (2020) assume for any function $g$ (not necessarily in $\mathcal{F}$), $\mathcal{T}g\in\mathcal{F}$, which is stronger than the completeness assumption presented in this paper (Assumption 2). low Eluder dimension problems can be efficiently learned in polynomial samples.

Assume $\mathcal{F}$ satisfies completeness (Assumption 2). Then for all $\epsilon>0$,

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.

In particular, the family of low BE dimension includes new examples such as kernel reactive POMDPs (Appendix B), which can not be addressed by the framework of either Bellman rank or Eluder dimension.

Algorithm Golf

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 near-optimal 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 Q-Iteration (FQI) (Szepesvári, 2010). Golf generalizes the Eleanor algorithm (Zanette et al., 2020a) 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 $\{\mathcal{D}_{h}\}_{h=1}^{H}$ to be empty sets, and confidence set $\mathcal{B}^{0}$ to be $\mathcal{F}$. Then, in each episode, Golf performs two main steps:

Line 3 (Optimistic planning): compute the most optimistic value function $f^{k}$ from the confidence set $\mathcal{B}^{k-1}$ constructed in the last episode , and choose $\pi^{k}$ to be its greedy policy.

Line 4-6 (Execute the policy and update the confidence set): execute policy $\pi^{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 $\mathcal{B}^{k}$. For each $h\in[H]$, Golf maintains a local regression constraint using the collected transition data $\mathcal{D}_{h}$ at this step

We remark that in general, the optimization problem in Line 3 of Golf can not be solved computationally efficiently.

In this subsection, we present the theoretical guarantees for Golf, which hold under Assumption 1 (realizability) and the following generalized completeness assumption introduced in Antos et al. (2008); Chen and Jiang (2019). Let $\mathcal{G}=\mathcal{G}_{1}\times\dots\times\mathcal{G}_{H}$ be an auxiliary function class provided to the learner where each $\mathcal{G}_{h}\subseteq(\mathcal{S}\times\mathcal{A}\rightarrow)$. Generalized completeness requires the auxiliary function class $\mathcal{G}$ to be rich enough so that applying Bellman operator to any function in the primary function class $\mathcal{F}$ will end up in $\mathcal{G}$.

$\mathcal{T}_{h}\mathcal{F}_{h+1}\subseteq\mathcal{G}_{h}$ for all $h\in[H]$.

If we choose $\mathcal{G}=\mathcal{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 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 $\sqrt{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.

By the standard online-to-batch argument, we also derive the sample complexity of Golf.

Under Assumption 1, 2, there exists an absolute constant $c$ such that for any $\epsilon\in(0,1]$, if we choose $\beta=c\log[\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(\epsilon^{2}/(dH^{2}))\cdot HK]$ in Golf, then the output policy $\pi^{\text{out}}$ is $\mathcal{O}(\epsilon)$-optimal with probability at least $1/2$, if

2 Key ideas in proving Theorem 15

In this subsection, we present a brief proof sketch for the regret bound of Golf. We defer all the details to Appendix D. For simplicity, we only discuss the case of choosing $\mathcal{D}_{\mathcal{F}}$ as the distribution family $\Pi$ in the definition of Bellman Eluder dimension (Definition 8). The proof for using $\mathcal{D}_{\Delta}$ as the distribution family follows from similar arguments.

Our proof strategy consists of three main steps.

We firstly show that, with high probability, the optimal value function $Q^{\star}$ indeed lies in the confidence set $\mathcal{B}^{k}$ for all $k\in[K]$ (Lemma 40 in Appendix D.1), which is a natural consequence of martingale concentration and the properties of the confidence set we designed. Because of $Q^{\star}\in\mathcal{B}^{k}$, the optimistic planning step (Line 3) in Golf guarantees that $V_{1}^{\star}(s_{1})\leq\max_{a}f_{1}^{k}(s_{1},a)$ for every episode $k$. This optimism allows the following upper bound on regret

Recall that our construction of the confidence set in Line 6 of Golf forces $f^{k}$ computed in episode $k$ to have a small loss $\mathcal{L}_{\mathcal{D}_{h}}$, which is a proxy for empirical squared Bellman error under data $\mathcal{D}_{h}$. Since data $\mathcal{D}_{h}$ in episode $k$ are collected by executing each $\pi^{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 D.1)

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 $\pi^{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 is a simplification of Lemma 41 in Appendix D, which is a modification of Lemma 2 in Russo and Van Roy (2013). Intuitively, Lemma 17 can be viewed as an analogue of the pigeon-hole principle for DE dimension. Choose $\Phi$ to be the function class of Bellman residuals, and $\mu_{k}$ to be the distribution under policy $\pi^{k}$, we finish the proof.

Algorithm Olive

In this section, we analyze algorithm Olive proposed in Jiang et al. (2017), which is based on hypothesis elimination. We prove that, despite Olive was originally designed for solving low Bellman rank problems, it naturally learns RL problems with low BE dimension as well.

The main advantage of Olive comparing to Golf is that Olive does not require the completeness assumption. In return, Olive has several disadvantages including worse sample complexity, and no sublinear regret.

The pseudocode of Olive is presented in Algorithm 2, where in each phase the algorithm contains the following three main components:

Line 3 (Optimistic planning): compute the most optimistic value function $f^{k}$ from the candidate set $\mathcal{B}^{k-1}$, and choose $\pi^{k}$ to be its greedy policy.

Line 4-7 (Estimate Bellman error): estimate the Bellman error of $f^{k}$ under $\pi^{k}$; output $\pi^{k}$ if the estimated error is small, and otherwise activate the elimination procedure.

Line 8-11 (Eliminate functions with large Bellman error): pick a step $t\in[H]$ where the estimated Bellman error exceeds the activation threshold $\zeta_{\text{act}}$; eliminate all functions in the candidate set whose Bellman error at step $t$ exceeds the elimination threshold $\zeta_{\text{elim}}$.

We comment that Olive is computationally inefficient in general because implementing the optimistic planning part requires solving an NP-hard problem in the worst case (Theorem 4, Dann et al., 2018).

Now, we are ready to present the theoretical guarantee for Olive.

Under Assumption 1, there exists absolute constant $c$ such that if we choose

Comparing to Golf, the major advantage of Olive is that Olive does not require completeness assumption (Assumption 2) to work. Nevertheless, Olive only learns the RL problems that have low BE dimension with respect to distribution family $\mathcal{D}_{\mathcal{F}}$, not $\mathcal{D}_{\Delta}$. The sample complexity of Olive is also worse than the sample complexity Golf (as presented in Corollary 16).

Finally, we comment that interpreting Olive through the lens of BE dimension, makes the proof of Theorem 18 surprisingly natural, which follows from the definition of BE dimension along with some standard concentration arguments.

2 Interpret Olive with BE dimension

In this subsection, we explain the key idea behind Olive through the lens of BE dimension.

To provide a clean high-level view, let us assume all estimates are accurate for now, and the activation threshold $\zeta_{\text{act}}$ and the elimination threshold $\zeta_{\text{elim}}$ satisfy $\zeta_{\text{elim}}\sqrt{d}\leq\zeta_{\text{act}}$, where d=\text{\dim_{\rm{BE}}}\big{(}\mathcal{F},\mathcal{D}_{\mathcal{F}},\zeta_{\text{act}}\big{)}. Since $\mathcal{E}(Q^{\star},\pi,h)\equiv 0$ for any $(\pi,h)$, $Q^{\star}$ is always in the candidate set. Therefore, the optimistic planning (Line 3) guarantees $\max_{a}f^{k}_{1}(s_{1},a)\geq V^{\star}_{1}(s_{1})$.

If the Bellman error summation is small (Line 6) i.e., $\sum_{h=1}^{H}\mathcal{E}(f^{k},\pi^{k},h)\leq H\zeta_{\rm act}$, then by simple policy loss decomposition (e.g., Lemma 1 in Jiang et al. (2017)) and the optimism of $f^{k}$, $\pi^{k}$ is $H\zeta_{\rm act}$-optimal. Otherwise, the elimination procedure is activated at some step $t$ satisfying $\mathcal{E}(f^{k},\pi^{k},t)\geq\zeta_{\rm act}$ and all $f$ with $\mathcal{E}(f,\pi^{k},t)\geq\zeta_{\rm elim}$ get eliminated. The key observation here is:

If the elimination procedure is activated at step $h$ in phase $k_{1}<\ldots<k_{m}$, then the roll-in distribution of $\pi^{k_{1}},\ldots,\pi^{k_{m}}$ at step $h$ is an $\zeta_{\text{act}}$-independent sequence with respect to the class of Bellman residuals $({I}-\mathcal{T}_{h})\mathcal{F}$ at step $h$. Therefore, we should have $m\leq d$.

For the sake of contradiction, assume $m\geq d+1$. Let us prove $\pi^{k_{1}},\ldots,\pi^{k_{d+1}}$ is a $\zeta_{\text{act}}$-independent sequence. Firstly, for any $j\in[d+1]$, since $f^{k_{j}}$ is not eliminated in phase $k_{1},\ldots,k_{j-1}$, we have

Besides, because the elimination procedure is activated at step $h$ in phase $k_{j}$, we have $\mathcal{E}(f^{k_{j}},\pi^{k_{j}},h)\geq\zeta_{\text{act}}$. By Definition 6, we obtain that the roll-in distribution of $\pi^{k_{j}}$ at step $h$ is $\zeta_{\text{act}}$-independent of those of $\pi^{k_{1}},\ldots,\pi^{k_{j-1}}$ for $j\in[d+1]$, which contradicts the definition d=\text{\dim_{\rm{BE}}}\big{(}\mathcal{F},\mathcal{D}_{\mathcal{F}},\zeta_{\text{act}}\big{)}. As a result, the elimination procedure can happen at most $d$ times for each $h\in[H]$, which means the algorithm should terminate within $dH+1$ phases and output an $H\zeta_{\rm act}$-optimal policy.

Conclusion

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.

References

Appendix A V-type BE Dimension and Algorithms

The definition of Bellman rank, mentioned in Definition 10 and Proposition 11, is slightly different from the original definition in Jiang et al. (2017). We denote the former by Q-type and the latter (the original definition) by V-type. In this section we introduce V-type BE Dimension as well as V-type variants of Golf and Olive. We show that similar results also hold for the V-type variants.

where $\|\phi_{h}(f)\|_{2}\cdot\|\psi_{h}(f^{\prime})\|_{2}\leq\zeta$, and $\zeta$ is the normalization parameter.

The only difference between these two definitions is how we sample $a_{h}$. In the Q-type definition we have $a_{h}\sim\pi_{f^{\prime}}$ (the roll-in policy), however in the V-type definition we have $a_{h}\sim\pi_{f}$ (the greedy policy of the function evaluated in the Bellman error) instead. It is worth mentioning that the Q-type and V-type bellman error coincide whenever $f=f^{\prime}$; namely, $\mathcal{E}(f,\pi_{f},h)=\mathcal{E}_{\textrm{V}}(f,\pi_{f},h)$ for all $f\in\mathcal{F}$.

We can similarly define the V-type variant of BE Dimension. At a high level, V-type BE dimension \text{\dim_{\rm{VBE}}}(\mathcal{F},\Pi,\epsilon) measures the complexity of finding a function in $\mathcal{F}$ such that its expected Bellman error under any state distribution in $\Pi$ is smaller than $\epsilon$.

Let $\Pi=\{\Pi_{h}\}_{h=1}^{H}$ be a collection of $H$ probability measure families over $\mathcal{S}$. The V-type $\epsilon$-BE dimension of $\mathcal{F}$ with respect to $\Pi$ is defined as

With slight abuse of notation, denote by $\mathcal{D}_{\mathcal{F},h}$ the collection of all probability measures over $\mathcal{S}$ at the $h^{\rm th}$ step, which can be generated by rolling in with a greedy policy $\pi_{f}$ with $f\in\mathcal{F}$. Similar to Proposition 11, the following proposition claims that the V-type BE dimension of $\mathcal{F}$ with respect to $\mathcal{D}_{\mathcal{F}}:=\{\mathcal{D}_{\mathcal{F},h}\}_{h\in[H]}$ is always upper bounded by its V-type Bellman rank up to some logarithmic factor.

If an MDP with function class $\mathcal{F}$ has V-type Bellman rank $d$ with normalization parameter $\zeta$, then

The proof of Proposition 21 is almost the same as that of Proposition 11 in Appendix C.1. We omit it here since the only modification is to replace Q-type Bellman rank with its V-type variant wherever it is used.

A.1 Algorithm V-type Golf

In this section we describe the V-type variant of Golf. The pseudocode is provided in Algorithm 3. Its only difference from the Q-type analogue is in Line 5: for each $h\in[H]$, we roll in with policy $\pi^{k}$ to sample $s_{h}$, and then instead of continuing following $\pi^{k}$ we take random action at step $h$.

Now we present the theoretical guarantee for Algorithm 3. Its proof is almost the same as that of Corollary 16 and can be found in appendix F.2.

Under Assumption 1, 14, there exists an absolute constant $c$ such that for any given $\epsilon>0$, if we choose $\beta=c\log[KH\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(\epsilon^{2}/(d|\mathcal{A}|H^{2}))]$, then with probability at least $0.99$, $\pi^{\rm out}$ is $\mathcal{O}(\epsilon)$-optimal, if

where d=\min_{\Pi\in\{\mathcal{D}_{\Delta},\mathcal{D}_{\mathcal{F}}\}}\text{\dim_{\rm{VBE}}}\big{(}\mathcal{F},\Pi,{\epsilon}/{H}\big{)}.

Compared with Theorem 23 (V-type Olive), Theorem 22 (V-type Golf) has the following two advantages.

The sample complexity in Theorem 22 depends linearly on the V-type BE-dimension while the dependence in Theorem 23 is quadratic.

Theorem 22 applies to RL problems of finite V-type BE dimension with respect to either $\mathcal{D}_{\mathcal{F}}$ or $\mathcal{D}_{\Delta}$. In comparison, Theorem 23 provides no guarantee for the $\mathcal{D}_{\Delta}$ case.

Finally, we comment that for the low Q-type BE dimension family, we provide both regret and sample complexity guarantees while for the low V-type counterpart, we only derive sample complexity result due to the need of taking actions uniformly at random in Algorithm 4 and Algorithm 3. Dong et al. (2020) propose an algorithm that can achieve $\sqrt{T}$-regret for problems of low V-type Bellman rank. It is an interesting open problem to study whether similar techniques can be adapted to the low V-type BE dimension setting so that we can also obtain $\sqrt{T}$-regret.

A.2 Algorithm V-type Olive

In this section, we describe the original Olive (i.e., V-type Olive) proposed by Jiang et al. (2017), and its theoretical guarantee in terms of V-type BE dimension.

The pseudocode is provided in Algorithm 4. Its only difference from Algorithm 2 is Line 9-10: note that V-type Bellman rank needs the action at step $t$ to be greedy with respect to the function $f$ instead of being picked by the roll-in policy $\pi^{k}$, so we choose action $a_{t}$ uniformly at random and use the importance-weighted estimator to estimate the Bellman error for each $f$.

We have the following similar theoretical guarantee for Algorithm 4. Its proof is almost the same as that of Theorem 18 and can be found in Appendix F.1.

Assume realizability (Assumption 1) holds and $\mathcal{F}$ is finite. There exists absolute constant $c$ such that if we choose

where d=\text{\dim_{\rm{VBE}}}\big{(}\mathcal{F},\mathcal{D}_{\mathcal{F}},{\epsilon}/{H}\big{)} and $\iota=c\log[Hd|\mathcal{A}|/\delta\epsilon]$, then with probability at least $1-\delta$, Algorithm 4 will output an $\mathcal{O}(\epsilon)$-optimal policy using at most $\mathcal{O}({H^{3}d^{2}|\mathcal{A}|\log(|\mathcal{F}|)\cdot\iota}/{\epsilon^{2}})$ episodes.

A.3 Discussions on Q-type versus V-type

In this paper, we have introduced two complementary definitions of Bellman rank: Q-type Bellman rank and V-type Bellman rank. And we prove they are upper bounds for Q-type and V-type BE dimension, respectively. Here, we want to emphasize that both Q-type and V-type Bellman rank have their own advantages. Specifically, the Q-type version has the following strengths.

There are natural RL problems whose Q-type Bellman rank is small, while their V-type Bellman rank is very large, e.g., the linear function approximation setting studied in in Zanette et al. (2020a).

All the existing sample complexity results for the V-type cases scale linearly with respect to the number of actions, while those for the Q-type cases are independent of the number of actions. Therefore, for control problems such as Linear Quadratic Regulator (LQR), which has both small Q-type and V-type Bellman rank but infinite number of actions, the notion of Q-type is more suitable.

On the other hand, there are problems that naturally induce low V-type Bellman rank but have large Q-type Bellman rank, e.g., reactive POMDPs.

Appendix B Examples

In this section, we introduce examples with low BE dimension. We will start with linear models and their variants, then introduce kernel MDPs, and finally present kernel reactive POMDPs which have low BE dimension, but possibly large Bellman rank and large Eluder dimension. All the proofs for this section are deferred to Appendix G.

In this subsection, we review problems with linear structure in ascending order of generality. We start with the definition of linear MDPs (e.g., Jin et al., 2020).

We remark that existing works (e.g., Jin et al., 2020) usually assumxe $\phi$ is known to the learner. Next, we review a more general setting—the linear completeness setting (e.g., Zanette et al., 2020a).

We make three comments here. Firstly, we note that linear MDPs automatically satisfy both linear realizability and linear completeness assumptions, therefore are special cases of the linear completeness setting with the same ambient dimension. Secondly, only assuming linear realizability but without completeness is insufficient for sample-efficient learning (see exponential lower bounds in Weisz et al. (2020)). Finally, as mentioned in Appendix A.3, though MDPs in the linear completeness setting have low Q-type Bellman rank, their V-type Bellman rank can be arbitrarily large.

Finally, we review the generalized linear completeness setting (Wang et al., 2019), which generalizes the linear completeness setting by adding nonlinearity.

One can directly verify by definition that when we choose link function $\sigma(x)=x$ in the generalized linear completeness setting, it will reduce to the standard linear version. Besides, it is known (Russo and Van Roy, 2013) the generalized linear completeness setting is a special case of low Eluder dimension, thus belonging to the low BE dimension family. Finally, we comment that despite the linear completeness setting belongs to the low Bellman rank family, the generalized version does not because of the possible nonlinearity of the link function.

B.2 Effective dimension and kernel MDPs

In this subsection, we introduce the notion of effective dimension. With this notion, we prove a useful proposition that any linear kernel function class with low effective dimension also has low Eluder dimension. This proposition directly implies that kernel MDPs are special cases of low Eluder dimension, which are also special cases of low BE dimension.

We start with the definition of effective dimension for a set, which is also known as critical information gain in Du et al. (2021).

The $\epsilon$-effective dimension of a set $\mathcal{X}$ is the minimum integer $d_{{\rm eff}}(\mathcal{X},\epsilon)=n$ such that

Based on this definition, we can also define the effective dimension of a function class.

Given a function class $\mathcal{F}$ defined on $\mathcal{X}$, its $\epsilon$-effective dimension $d_{{\rm eff}}(\mathcal{F},\epsilon)=n$ is the minimum integer $n$ such that there exists a separable Hilbert space $\mathcal{H}$ and a mapping $\phi:\mathcal{X}\rightarrow\mathcal{H}$ so that

for every $f\in\mathcal{F}$ there exists $\theta_{f}\in B_{\mathcal{H}}(1)$ satisfying $f(x)=\langle\theta_{f},\phi(x)\rangle_{\mathcal{H}}$ for all $x\in\mathcal{X}$,

$d_{{\rm eff}}(\phi(\mathcal{X}),\epsilon)=n$ where $\phi(\mathcal{X})=\{\phi(x):\ x\in\mathcal{X}\}$.

The following proposition shows that the Eluder dimension of any function class is always upper bounded by its effective dimension.

For any function class $\mathcal{F}$ and domain $\mathcal{X}$, we have

On the other hand, we remark that effective dimension requires the existence of a benign linear structure in certain Hilbert spaces. In constrast, Eluder dimension does not require such conditions. Therefore, the function class of low Eluder dimension is more general than the function class of low effective dimension.

Now, we are ready to define kernel MDPs and prove it is a subclass of low Eluder dimension.

$\|\theta_{h}^{r}\|_{\mathcal{H}}\leq 1$ and $\|\phi_{h}(s,a)\|_{\mathcal{H}}\leq 1$ for all $s,a$.

$\|\sum_{s\in\mathcal{S}}\mathcal{V}(s)\psi_{h}({s})\|_{\mathcal{H}}\leq 1$ for any function $\mathcal{V}:\mathcal{S}\rightarrow$.

$\dim_{\rm eff}(\mathcal{X}_{h},\epsilon)\leq d(\epsilon)$ for all $h$ and $\epsilon$, where $\mathcal{X}_{h}=\{\phi_{h}(s,a):~{}(s,a)\in\mathcal{S}\times\mathcal{A}\}$.

In order to learn kernel MDPs, we need to construct a proper function class $\mathcal{F}$. Formally, for each $h\in[H]$, we choose $\mathcal{F}_{h}=\{\phi_{h}(\cdot,\cdot)^{\top}\theta~{}\mid~{}\theta\in B_{\mathcal{H}}(H+1-h)\}$. One can easily verify $\mathcal{F}$ satisfies both realizability and completeness by following the same arguments as in linear MDPs (Jin et al., 2020). In order to apply Golf or Olive, we also need to show it has low BE dimension and bounded log-covering number. Below, we prove in sequence that $\mathcal{F}$ has low Eluder dimension and low log-covering number. Therefore, kernel MDPs fall into our low BE dimension framework.

Let $\mathcal{M}$ be a kernel MDP of effective dimension $d(\epsilon)$, then

Proposition 31 follows directly from Proposition 29 by rescaling the parameters. Utilizing Proposition 31, we can further prove the log-covering number of $\mathcal{F}$ is also upper bounded by the effective dimension of the kernel MDP up to some logarithmic factor.

Let $\mathcal{M}$ be a kernel MDP of effective dimension $d(\epsilon)$, then

B.3 Effective Bellman rank and kernel reactive POMDPs

To begin with, we introduce the definition of effective Bellman rank and prove that it is always an upper bound for BE dimension. We will see effective Bellman rank serves as a useful tool for controlling the BE dimension of the example discussed in this section—kernel reactive POMDPs.

We start with Q-type $\epsilon$-effective Bellman rank which is simply the $\epsilon$-effective dimension of a special feature set.

The Q-type $\epsilon$-effective Bellman rank is the minimum integer $d$ so that

There exists $\phi_{h}:\mathcal{F}\rightarrow\mathcal{H}$ and $\psi_{h}:\mathcal{F}\rightarrow\mathcal{H}$ for each $h\in[H]$ where $\mathcal{H}$ is a separable Hilbert space, such that for any $f,f^{\prime}\in\mathcal{F}$, the average Bellman error

where $\|\phi_{h}(f)\|_{\mathcal{H}}\leq\zeta$, and $\zeta$ is the normalization parameter.

$d=\max_{h\in[H]}d_{\rm eff}(\mathcal{X}_{h}(\psi,\mathcal{F}),\epsilon/\zeta)$ where $\mathcal{X}_{h}(\psi,\mathcal{F})=\{\psi_{h}(f_{h}):\ f_{h}\in\mathcal{F}_{h}\}$.

One can easily verify that when $\mathcal{H}$ is a finite-dimensional Euclidean space, the $\epsilon$-effective Bellman rank is always upper bounded by the original Bellman rank up to a logarithmic factor in $\zeta$ and $\epsilon^{-1}$. Moreover, the effective Bellman rank can be much smaller than the original Bellman rank if the induced feature set $\{\mathcal{X}_{h}(\psi,\mathcal{F})\}_{h\in[H]}$ approximately lies in a low-dimensional linear subspace. Therefore, effective Bellman rank can be viewed as a strict generalization of the original version.

Suppose function class $\mathcal{F}$ has Q-type $\epsilon$-effective Bellman rank $d$, then

Proposition 34 claims that problems with low Q-type effective Bellman rank also have low Q-type BE dimension.

We can similarly define the V-type variant of effective Bellman rank, and prove it is always an upper bound for V-type BE dimension.

The V-type $\epsilon$-effective Bellman rank is the minimum integer $d$ so that

There exists $\phi_{h}:\mathcal{F}\rightarrow\mathcal{H}$ and $\psi_{h}:\mathcal{F}\rightarrow\mathcal{H}$ for each $h\in[H]$ where $\mathcal{H}$ is a separable Hilbert space, such that for any $f,f^{\prime}\in\mathcal{F}$, the average Bellman error

where $\|\phi_{h}(f)\|_{\mathcal{H}}\leq\zeta$, and $\zeta$ is the normalization parameter.

$d=\max_{h\in[H]}d_{\rm eff}(\mathcal{X}_{h}(\psi,\mathcal{F}),\epsilon/\zeta)$ where $\mathcal{X}_{h}(\psi,\mathcal{F})=\{\psi_{h}(f_{h}):\ f_{h}\in\mathcal{F}_{h}\}$.

Suppose function class $\mathcal{F}$ has V-type $\epsilon$-effective Bellman rank $d$, then

The proof of Proposition 36 is almost the same as that of Proposition 34. We omit it since the only modification is to replace Q-type effective Bellman rank with its V-type variant wherever it is used.

We want to briefly comment that the majority of examples introduced in Du et al. (2021) have low effective Bellman rank. For example, low occupancy complexity, linear $Q^{*}/V^{*}$, linear Bellman complete and $Q^{*}$ state aggregation have low Q-type effective Bellman rank. And the feature selection problem has low V-type Bellman rank.

A kernel reactive POMDP is a POMDP that additionally satisfies the following two conditions

(Reactiveness) The optimal action-value function $Q^{*}$ only depends on the current observation and action, i.e., for each $h\in[H]$, there exists function $f^{*}_{h}:\mathcal{O}\times\mathcal{A}\rightarrow$ such that for all $\tau_{h}=[o_{1},a_{1},r_{1},\ldots,o_{h}]$ and $a_{h}$

The following proposition shows that when a kernel reactive POMDP has low effective dimension, it also has low V-type BE dimension.

Any kernel reactive POMDP and function class $\mathcal{F}\subseteq(\mathcal{O}\times\mathcal{A}\rightarrow)$ satisfy

We comment that when $\mathcal{H}$ approximately aligns with a low-dimensional linear subspace, the V-type effective Bellman rank in Proposition 38 will also be low. However, the Eluder dimension of $\mathcal{F}$ can be arbitrarily large because we basically pose no structural assumption on $\mathcal{F}$. Besides, its V/Q-type original Bellman rank can also be arbitrarily large, because $\mathcal{H}$ may be infinite-dimensional and the observation set $\mathcal{O}$ may be exponentially large. If we additionally assume $\mathcal{F}$ satisfies realizability ($f^{*}\in\mathcal{F}$), then we can apply V-type Olive and obtain polynomial sample-complexity guarantee.

Appendix C Proofs for BE Dimension

In this section, we provide formal proofs for the results stated in Section 3.

The proof is basically the same as that of Example 3 in Russo and Van Roy (2013) with minor modification.

By the definition of Bellman rank, this is equivalent to: for all $i\in[m]$, $\sqrt{\sum_{t=1}^{i-1}(\langle\phi_{h}(g^{i}),\psi_{h}(f^{t})\rangle)^{2}}\leq\epsilon$ and $|\langle\phi_{h}(g^{i}),\psi_{h}(f^{i})\rangle|>\epsilon$.

For notational simplicity, define $\mathbf{x}_{i}=\phi_{h}(g^{i})$, $\mathbf{z}_{i}=\psi_{h}(f^{i})$ and $\mathbf{V}_{i}=\sum_{t=1}^{i-1}\mathbf{z}_{t}\mathbf{z}_{t}^{\top}+\frac{\epsilon^{2}}{\zeta}\cdot\mathbf{I}$. The previous argument directly implies: for all $i\in[m]$, $\|\mathbf{x}_{i}\|_{\mathbf{V}_{i}}\leq\sqrt{2}\epsilon$ and $\|\mathbf{x}_{i}\|_{\mathbf{V}_{i}}\cdot\|\mathbf{z}_{i}\|_{\mathbf{V}_{i}^{-1}}>\epsilon$. Therefore, we have $\|\mathbf{z}_{i}\|_{\mathbf{V}_{i}^{-1}}\geq\frac{1}{\sqrt{2}}$.

C.2 Proof of Proposition 12

Assume $\delta_{z_{1}},\ldots,\delta_{z_{m}}$ is an $\epsilon$-independent sequence of distributions with respect to $(I-\mathcal{T}_{h})\mathcal{F}$, where $\delta_{z_{i}}\in\mathcal{D}_{\Delta}$. By Definition 6, there exist functions $f^{1},\ldots,f^{m}\in\mathcal{F}$ such that for all $i\in[m]$, we have $|(f^{i}_{h}-\mathcal{T}_{h}f^{i}_{h+1})(z_{i})|>\epsilon$ and $\sqrt{\sum_{t=1}^{i-1}|(f^{i}_{h}-\mathcal{T}_{h}f^{i}_{h+1})(z_{t})|^{2}}\leq\epsilon$. Define $g^{i}_{h}=\mathcal{T}_{h}f^{i}_{h+1}$. Note that $g^{i}_{h}\in\mathcal{F}_{h}$ because $\mathcal{T}_{h}\mathcal{F}_{h+1}\subset\mathcal{F}_{h}$. Therefore, we have for all $i\in[m]$, $|(f^{i}_{h}-g^{i}_{h})(z_{i})|>\epsilon$ and $\sqrt{\sum_{t=1}^{i-1}|(f^{i}_{h}-g^{i}_{h})(z_{t})|^{2}}\leq\epsilon$ with $f^{i}_{h},g_{h}^{i}\in\mathcal{F}_{h}$. By Definition 4 and 5, this implies $\dim_{\rm E}(\mathcal{F}_{h},\epsilon)\geq m$, which completes the proof. ∎

C.3 Proof of Proposition 13

The function set $\mathcal{F}_{1}=\{f_{\theta_{i}}(a)=a^{\top}\theta_{i}:\ \theta_{i}=(1;e_{i}),\ i\in[m]\}$.

The reward function is always zero, i.e., $r\equiv 0$.

For any $\epsilon\in(0,1]$, $a_{1},\ldots,a_{m-1}$ is an $\epsilon$-independent sequence of points because: (a) for any $t\in[m-1]$, $\sum^{t-1}_{i=1}(f_{\theta_{t}}(a_{i})-f_{\theta_{t+1}}(a_{i}))^{2}=0$; (b) for any $t\in[m-1]$, $f_{\theta_{t}}(a_{t})-f_{\theta_{t+1}}(a_{t})=1\geq\epsilon$. Therefore, $\min_{h\in[H]}\dim_{\rm E}(\mathcal{F}_{h},\epsilon)=\dim_{\rm E}(\mathcal{F}_{1},\epsilon)\geq m-1$.

Appendix D Proofs for Golf

In this section, we provide formal proofs for the results stated in Section 4.

We start the proof with the following two lemmas. The first lemma shows that with high probability any function in the confidence set has low Bellman-error over the collected datasets $\mathcal{D}_{1},\ldots,\mathcal{D}_{H}$ as well as the distributions from which $\mathcal{D}_{1},\ldots,\mathcal{D}_{H}$ are sampled.

Let $\rho>0$ be an arbitrary fixed number. If we choose \beta=c\big{(}\log[KH\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(\rho)/\delta]+K\rho\big{)} with some large absolute constant $c$ in Algorithm 1, then with probability at least $1-\delta$, for all $(k,h)\in[K]\times[H]$, we have

$\sum_{i=1}^{k-1}{\left(f^{k}_{h}(s_{h}^{i},a_{h}^{i})-(\mathcal{T}f_{h+1}^{k})(s_{h}^{i},a_{h}^{i})\right)}^{2}{\leq}\mathcal{O}(\beta)$,

where $(s_{1}^{i},a_{1}^{i},\ldots,s_{H}^{i},a_{H}^{i},s_{H+1}^{i})$ denotes the trajectory sampled by following $\pi^{i}$ in the $i^{\rm th}$ episode.

The second lemma guarantees that the optimal value function is inside the confidence with high probability. As a result, the selected value function $f^{k}$ in each iteration shall be an upper bound of $Q^{\star}$ with high probability.

Under the same condition of Lemma 39, with probability at least $1-\delta$, we have $Q^{\star}\in\mathcal{B}^{k}$ for all $k\in[K]$.

The proof of Lemma 39 and 40 relies on standard martingale concentration (e.g. Freedman’s inequality) and can be found in Appendix D.3.

By Lemma 40, we can upper bound the cumulative regret by the summation of Bellman error with probability at least $1-\delta$:

where $(i)$ follows from standard policy loss decomposition (e.g. Lemma 1 in Jiang et al. (2017)).

Next, we focus on a fixed step $h$ and bound the cumulative Bellman error $\sum_{k=1}^{K}\mathcal{E}(f^{k},\pi^{k},h)$ using Lemma 39. To proceed, we need the following lemma to control the accumulating rate of Bellman error.

Lemma 41 is a simple modification of Lemma 2 in Russo and Van Roy (2013) and its proof can be found in Appendix D.4. We provide two ways to apply Lemma 41, which can produce regret bounds in term of two different complexity measures. If we invoke Lemma 39 (a) and Lemma 41 with

We can also invoke Lemma 39 (b) and Lemma 41 with

where the first inequality follows from standard martingale concentration.

Plugging either equation (8) or (9) back into equation (7) completes the proof.

D.2 Proof of Corollary 16

By Lemma 40, we can upper bound the cumulative regret by the summation of Bellman error with probability at least $1-\delta$:

where $(i)$ follows from standard policy loss decomposition (e.g. Lemma 1 in Jiang et al. (2017)).

Next, we focus on a fixed step $h$ and bound the cumulative Bellman error $\sum_{k=1}^{K}\mathcal{E}(f^{k},\pi^{k},h)$ using Lemma 39.

we obtain with probability at least $1-10^{-3}$,

where the second inequality follows from the choice of $\rho$ and d:=\text{\dim_{\rm{BE}}}(\mathcal{F},\mathcal{D}_{\mathcal{F}},\epsilon/H). Now we need to choose $K$ such that

By simple calculation, one can verify it suffices to choose

Plugging equation (11) back into equation (10) completes the proof. We can similarly prove the bound in terms of the BE dimension with respect to $\mathcal{D}_{\Delta}$.

D.3 Proofs of concentration lemmas

To begin with, recall the Freedman’s inequality that controls the sum of martingale difference by the sum of their predicted variance.

and $\mathfrak{F}_{t,h}$ be the filtration induced by $\{s_{1}^{i},a_{1}^{i},r_{1}^{i},\ldots,s_{H}^{i}\}_{i=1}^{t-1}\bigcup\{s_{1}^{t},a_{1}^{t},r_{1}^{t},\ldots,s_{h}^{t},a_{h}^{t}\}$. We have

By Freedman’s inequality, we have, with probability at least $1-\delta$,

Let $\mathcal{Z}_{\rho}$ be a $\rho$-cover of $\mathcal{F}$. Now taking a union bound for all $(k,h,\phi)\in[K]\times[H]\times\mathcal{Z}_{\rho}$, we obtain that with probability at least $1-\delta$, for all $(k,h,\phi)\in[K]\times[H]\times\mathcal{Z}_{\rho}$

where $\iota=\log(HK|\mathcal{Z}_{\rho}|/\delta)$. From now on, we will do all the analysis conditioning on this event being true.

Consider an arbitrary $(h,k)\in[H]\times[K]$ pair. By the definition of $\mathcal{B}^{k}$ and Assumption 14

Putting (15) and (16) together, we obtain

Because $\phi^{k}$ is an $\rho$-approximation to $f^{k}$, we conclude

Therefore, we prove inequality $(b)$ in Lemma 39.

To prove inequality $(a)$, we only need to redefine $\mathfrak{F}_{t,h}$ to be the filtration induced by $\{s_{1}^{i},a_{1}^{i},r_{1}^{i},\ldots,s_{H}^{i}\}_{i=1}^{t-1}$ and then repeat the arguments above verbatim. ∎

D.3.2 Proof of Lemma 40

Let $\mathcal{V}_{\rho}$ be a $\rho$-cover of $\mathcal{G}$.

Consider an arbitrary fixed tuple $(k,h,g)\in[K]\times[H]\times\mathcal{G}$. Let

and $\mathfrak{F}_{t,h}$ be the filtration induced by $\{s_{1}^{i},a_{1}^{i},r_{1}^{i},\ldots,s_{H}^{i}\}_{i=1}^{t-1}\bigcup\{s_{1}^{t},a_{1}^{t},r_{1}^{t},\ldots,s_{h}^{t},a_{h}^{t}\}$. We have

By Freedman’s inequality, with probability at least $1-\delta$,

By taking a union bound over $[K]\times[H]\times\mathcal{V}_{\rho}$ and the non-negativity of $\sum_{t=1}^{k}[(g_{h}-Q_{h}^{\star})(s_{h}^{t},a_{h}^{t})]^{2}$, we obtain that with probability at least $1-\delta$, for all $(k,h,\psi)\in[K]\times[H]\times\mathcal{V}_{\rho}$

where $\iota=\log(HK|\mathcal{V}_{\rho}|/\delta)$. This directly implies for all $(k,h,g)\in[K]\times[H]\times\mathcal{G}$

Finally, by recalling the definition of $\mathcal{B}^{k}$, we conclude that with probability at least $1-\delta$, $Q^{\star}\in\mathcal{B}^{k}$ for all $k\in[K]$. ∎

D.4 Proof of Lemma 41

resulting in $L\leq{\beta}/{\epsilon^{2}}$.

For $t\in[k]$, we want to prove that if $e_{t}>\omega$, then we have $e_{t}\leq\min\{\sqrt{\frac{d\beta}{t-d}},C\}$. Assume $t\in[k]$ satisfies $e_{t}>\omega$. Then there exists $\alpha$ such that $e_{t}>\alpha\geq\omega$. By Proposition 43, we have

which implies $\alpha\leq\sqrt{\frac{d\beta}{t-d}}$. Besides, recall $e_{t}\leq C$, so we have $e_{t}\leq\min\{\sqrt{\frac{d\beta}{t-d}},C\}$.

Appendix E Proofs for Olive

In this section, we provide the formal proof for the results stated in Appendix 5.

By standard concentration arguments (Hoeffding’s inequality plus union bound argument), with probability at least $1-\delta$, the following events hold for the first $dH+1$ phases (please refer to Appendix E.2 for the proof)

If the elimination procedure is activated at the $h^{\rm th}$ step in the $k^{\rm th}$ phase, then $\mathcal{E}(f^{k},\pi^{k},h)>\zeta_{\rm act}/2$ and all $f\in\mathcal{F}$ satisfying $|\mathcal{E}(f,\pi^{k},h)|\geq 2\zeta_{\rm elim}$ get eliminated.

If the elimination procedure is not activated in the $k^{\rm th}$ phase, then, $\sum_{h=1}^{H}\mathcal{E}(f^{k},\pi^{k},h)<2H\zeta_{\rm act}=4\epsilon$.

Therefore, if we can show Olive terminates within $dH+1$ phases, then with high probability the output policy is $4\epsilon$-optimal by the optimism of $f^{k}$ and simple policy loss decomposition (e.g. Lemma 1 in Jiang et al. (2017)):

In order to prove that Olive terminates within $dH+1$ phases, it suffices to show that for each $h\in[H]$, we can activate the elimination procedure at the $h^{\rm th}$ step for at most $d$ times.

For the sake of contradiction, assume that Olive does not terminate in $dH+1$ phases. Within these $dH+1$ phases, there exists some $h\in[H]$ for which the activation process has been activated for at least $d+1$ times. Denote by $k_{1}<\cdots<k_{d+1}\leq dH+1$ the indices of the phases where the elimination is activated at the $h^{\rm th}$ step. By the high-probability events, for all $i<j\leq d+1$, we have $|\mathcal{E}(f^{k_{j}},\pi^{k_{i}},h)|<2\zeta_{\rm elim}$ and for all $l\leq d+1$, we have $\mathcal{E}(f^{k_{l}},\pi^{{k_{l}}},h)>\zeta_{\rm act}/2$. This means for all $l\leq d+1$, we have both \sqrt{\sum_{i=1}^{l-1}\big{(}\mathcal{E}(f^{k_{l}},\pi^{{k_{i}}},h)\big{)}^{2}}<\sqrt{d}\times 2\zeta_{\rm elim}=\epsilon/H and $\mathcal{E}(f^{k_{l}},\pi^{{k_{l}}},h)>\zeta_{\rm act}/2=\epsilon/H$. Therefore, the roll-in distribution of $\pi^{k_{1}},\ldots,\pi^{k_{d+1}}$ at step $h$ is an $\epsilon/H$-independent sequence of length $d+1$, which contradicts with the definition of BE dimension. So Olive should terminate within $dH+1$ phases.

In sum, with probability at least $1-\delta$, Algorithm 2 will terminate and output a $4\epsilon$-optimal policy using at most

E.2 Concentration arguments for Theorem 18

where d=\max_{h\in[H]}\text{\dim_{\rm{BE}}}\big{(}\mathcal{F},\mathcal{D}_{\mathcal{F},h},\epsilon/H\big{)}, $\iota=\log[Hd/\delta\epsilon]$ and $c$ is a large absolute constant.Our goal is to prove with probability at least $1-\delta$, the following events hold for the first $dH+1$ phases

If the elimination procedure is activated at the $h^{\rm th}$ step in the $k^{\rm th}$ phase, then $\mathcal{E}(f^{k},\pi^{k},h)>\zeta_{\rm act}/2$ and all $f\in\mathcal{F}$ satisfying $|\mathcal{E}(f,\pi^{k},h)|\geq 2\zeta_{\rm elim}$ get eliminated.

If the elimination procedure is not activated in the $k^{\rm th}$ phase, then, $\sum_{h=1}^{H}\mathcal{E}(f^{k},\pi^{k},h)<2H\zeta_{\rm act}=4\epsilon$.

Consider a fixed $(k,h)\in[dH+1]\times[H]$ pair. By Azuma-Hoefdding’s inequality, with probability at least $1-\frac{\delta}{8H(dH^{2}+1)}$, we have

where the second inequality follows from $n_{\text{act}}=C\frac{H^{2}\iota}{\epsilon^{2}}$ with $C$ being chosen large enough.

Take a union bound for all $(k,h)\in[dH+1]\times[H]$, we have with probability at least $1-{\delta}/4$, the following holds for all $(k,h)\in[dH+1]\times[H]$

By Algorithm 2, if the elimination procedure is not activated in the $k^{\rm th}$ phase, we have $\sum_{h=1}^{H}\hat{\mathcal{E}}(f^{k},\pi^{k},h)\leq H\zeta_{\rm act}$. Combine it with the concentration argument we just proved,

On the other hand, if the elimination procedure is activated at the $h^{\rm th}$ step in the $k^{\rm th}$ phase, then $\hat{\mathcal{E}}(f^{k},\pi^{k},h)>\zeta_{\rm act}$. Again combine it with the concentration argument we just proved,

Recall that Algorithm 2 eliminates all $f$ satisfying $|\hat{\mathcal{E}}(f,\pi^{k},h_{k})|>\zeta_{\rm elim}$ when the elimination procedure is activated at the $h^{\rm th}_{k}$ step in the $k^{\rm th}$ phase. Therefore, if $|\mathcal{E}(f,\pi^{k},h_{k})|\geq 2\zeta_{\rm elim}$, $f$ will be eliminated because

Finally, note that $\mathcal{E}(Q^{\star},\pi,h)\equiv 0$ for any $\pi$ and $h$. As a result, it will never be eliminated within the first $dH+1$ phases because we can similarly prove

Wrapping up: take a union bound for the activation and elimination procedure, and conclude that the three events, listed at the beginning of this section, hold for the the first $dH+1$ phases with probability at least $1-\delta/2$.

Appendix F Proofs for V-type Variants

In this section, we provide formal proofs for the results stated in Section A.

The proof is similar to that in Appendix E.

By standard concentration arguments (Hoeffding’s inequality, Bernstein’s inequality, and union bound argument), with probability at least $1-\delta$, the following events hold for the first $dH+1$ phases (please refer to Appendix F.1.1 for the proof)

If the elimination procedure is activated at the $h^{\rm th}$ step in the $k^{\rm th}$ phase, then $\mathcal{E}_{\textrm{V}}(f^{k},\pi^{k},h)>\zeta_{\rm act}/2$ and all $f\in\mathcal{F}$ satisfying $|\mathcal{E}_{\textrm{V}}(f,\pi^{k},h)|\geq 2\zeta_{\rm elim}$ get eliminated.

If the elimination procedure is not activated in the $k^{\rm th}$ phase, then, $\sum_{h=1}^{H}\mathcal{E}_{\textrm{V}}(f^{k},\pi^{k},h)<2H\zeta_{\rm act}=4\epsilon$.

Therefore, if we can show Olive terminates within $dH+1$ phases, then with high probability the output policy is $4\epsilon$-optimal by the optimism of $f^{k}$ and simple policy loss decomposition (e.g., Lemma 1 in Jiang et al. (2017)):

In order to prove that Olive terminates within $dH+1$ phases, it suffices to show that for each $h\in[H]$, we can activate the elimination procedure at the $h^{\rm th}$ step for at most $d$ times.

For the sake of contradiction, assume that Olive does not terminate in $dH+1$ phases. Within these $dH+1$ phases, there exists some $h\in[H]$ for which the activation process has been activated for at least $d+1$ times. Denote by $k_{1}<\cdots<k_{d+1}\leq dH+1$ the indices of the phases where the elimination is activated at the $h^{\rm th}$ step. By the high-probability events, for all $i<j\leq d+1$, we have $|\mathcal{E}_{\textrm{V}}(f^{k_{j}},\pi^{k_{i}},h)|<2\zeta_{\rm elim}$ and for all $l\leq d+1$, we have $\mathcal{E}_{\textrm{V}}(f^{k_{l}},\pi^{{k_{l}}},h)>\zeta_{\rm act}/2$. This means for all $l\leq d+1$, we have both \sqrt{\sum_{i=1}^{l-1}\big{(}\mathcal{E}_{\textrm{V}}(f^{k_{l}},\pi^{{k_{i}}},h)\big{)}^{2}}<\sqrt{d}\times 2\zeta_{\rm elim}=\epsilon/H and $\mathcal{E}_{\textrm{V}}(f^{k_{l}},\pi^{{k_{l}}},h)>\zeta_{\rm act}/2=\epsilon/H$. Therefore, the roll-in distribution of $\pi^{k_{1}},\ldots,\pi^{k_{d+1}}$ at step $h$ is an $\epsilon/H$-independent sequence of length $d+1$ with respect to $(I-\mathcal{T}_{h})V_{\mathcal{F}}$, which contradicts with the definition of BE dimension. So Olive should terminate within $dH+1$ phases.