Batch Value-function Approximation with Only Realizability

Introduction

What is the minimal function-approximation assumption that enables polynomial sample complexity, when we try to learn $Q^{\star}$ from an exploratory batch dataset? Existing algorithms and analyses—those that have largely laid the theoretical foundation of modern reinforcement learning—have always demanded assumptions that are substantially stronger than the most basic one: realizability, i.e., that $Q^{\star}$ (approximately) lies in the function class. These strong assumptions have recently compelled Chen & Jiang (2019) to conjecture an information-theoretic barrier, that polynomial learning is impossible in batch RL, even with exploratory data and realizable function approximation.

In this paper, we break this barrier by an algorithm called Batch Value-Function Tournament (BVFT). Via a tournament procedure, BVFT reduces the learning problem to that of identifying $Q^{\star}$ from a pair of candidate functions. In this subproblem, we create a piecewise constant function class of statistical complexity $O(1/\epsilon^{2})$ that can express both candidate functions up to small discretization errors, and use the projected Bellman operator associated with the class to identify $Q^{\star}$. We present the algorithm in Section 4 and prove its sample complexity in Sections 5 and 6. A limitation of our approach is the use of a relatively stringent version of concentrability coefficient from Munos (2003) to measure the exploratoriness of the dataset (see Assumption 1). Section 7.2 investigates the difficulties in relaxing the assumption, and Appendix D discusses how to mitigate the pathological behavior of the algorithm when the assumption does not hold.

As another limitation, BVFT enumerates over the function class and is computationally inefficient for training. That said, the algorithm is efficient when the function class has a polynomial cardinality, making it applicable to another problem in batch RL: model selection (Farahmand & Szepesvári, 2011).We use the phrase “model selection” as in the context of e.g., cross validation, and the word “model” does not refer to MDP dynamics; rather they refer to value functions for our purposes. In Section 7.1, we review the literature on this important problem and discuss how BVFT has significantly advanced the state of the art on the theoretical front.

Related Work

Stronger Function-Approximation Assumptions in Existing Theory The theory of batch RL has struggled for a long time to provide sample-efficiency guarantees when realizability is the only assumption imposed on the function class. An intuitive reason is that learning $Q^{\star}$ is roughly equivalent to minimizing the Bellman error, but the latter cannot be estimated from data (Jiang, 2019; Sutton & Barto, 2018, Chapter 11.6), leading to the infamous “double sampling” difficulty (Baird, 1995; Antos et al., 2008). Stronger/additional assumptions have been proposed to circumvent the issue, including low inherent Bellman errors (Munos & Szepesvári, 2008; Antos et al., 2008), averager classes (Gordon, 1995), and additional function approximation of importance weights (Xie & Jiang, 2020).

State Abstractions State abstractions are the simplest form of function approximation. (They are also special cases of the aforementioned averagers.) In fact, certainty equivalence with a state abstraction that can express $Q^{\star}$, known as $Q^{\star}$-irrelevant abstractions, is known to be consistent, i.e., $Q^{\star}$ will be correctly learned if each abstract state-action pair receives infinite amount of data (Littman & Szepesvári, 1996; Li et al., 2006, Theorem 4).

Tournament Algorithms Our algorithm design also draws inspirations from existing tournament algorithms. Closest related is Scheffé tournament for density estimation (Devroye & Lugosi, 2012), which minimizes the total-variation (TV) distance from the true density among the candidate models, and has been applied to RL by Sun et al. (2019). Interestingly, the main challenge in TV-distance minimization is very similar to ours at a high level, that TV-distance itself of a single model cannot be estimated from data when the support of the distribution has a large or infinite cardinality. Similar to Scheffé tournament, our algorithm compares pairs of candidate value functions, which is key to overcoming the fundamental unlearnability of Bellman errors.

Tournament algorithms are also found in RL when the goal is to select the best state abstraction from a candidate set (Hallak et al., 2013; Jiang et al., 2015). These works will be discussed in Section 7.1 in the context of model selection.

Lower Bounds Wang et al. (2020); Amortila et al. (2020); Zanette (2020); Chen et al. (2021) have recently proved hardness results under $Q^{\star}$ realizability in batch RL. These results do not contradict ours because they deploy a weaker data assumption; see Appendix A.2 for discussions. Rather, their negative and our positive results are complementary and together provide a fine-grained characterization of the landscape of batch RL.

Preliminaries

Consider an infinite-horizon discounted Markov Decision Process $(\mathcal{S},\mathcal{A},P,R,\gamma,d_{0})$, where $\mathcal{S}$ is the finite state space that can be arbitrarily large, $\mathcal{A}$ is the finite action space, $P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the transition function, $R:\mathcal{S}\times\mathcal{A}\to[0,R_{\max}]$ is the reward function, $\gamma\in[0,1)$ is the discount factor, and $d_{0}\in\Delta(\mathcal{S})$ is the initial state distribution.

2 Batch Data

We assume that the learner has access to a batch dataset $D$ consisting of i.i.d. $(s,a,r,s^{\prime})$ tuples, where $(s,a)\sim\mu,r=R(s,a),s^{\prime}\sim P(s,a)$. Such an i.i.d. assumption is standard for finite-sample analyses in the ADP literature (Munos & Szepesvári, 2008; Farahmand et al., 2010; Chen & Jiang, 2019), and can often be relaxed at the cost of significant technical burdens and complications (see e.g., Antos et al., 2008). We will also use $\mu(s)$ and $\mu(a|s)$ to denote the marginal of $s$ and the conditional of $a$ given $s$. To learn a near-optimal policy in batch RL, an exploratory dataset is necessary, and we measure the degree of exploration as follows:

We assume that $\mu(s,a)>0~{}\forall s,a$. We further assume that (1) There exists constant $1\leq C_{\mathcal{A}}<\infty$ such that for any $s\in\mathcal{S},a\in\mathcal{A}$, $\mu(a|s)\geq 1/C_{\mathcal{A}}$. (2) There exists constant $1\leq C_{\mathcal{S}}<\infty$ such that for any $s\in\mathcal{S},a\in\mathcal{A},s^{\prime}\in\mathcal{S}$, $P(s^{\prime}|s,a)/\mu(s^{\prime})\leq C_{\mathcal{S}}$. Also $d_{0}(s)/\mu(s)\leq C_{\mathcal{S}}$. It will be convenient to define $C=C_{\mathcal{S}}C_{\mathcal{A}}$.

The first statement is very standard, asserting that the data distribution put enough probabilities on all actions. For example, with a small number of actions, a uniformly random policy ensures that $C_{\mathcal{A}}=|\mathcal{A}|$ satisfies this assumption.

The second statement measures the exploratoriness of $\mu$’s state marginal by $C_{\mathcal{S}}$, and two comments are in order. First, this is a form of concentrability assumption, which not only enforces data to be exploratory, but also implicitly imposes restrictions on the MDP’s dynamics (see the reference to $P$ in Assumption 1). While the latter may be undesirable, Chen & Jiang (2019, Theorem 4) shows that such a restriction is unavoidable when learning with a general function class. Second, the version of concentrability coefficient we use was introduced by Munos (2003, Eq.(6)), and is more stringent than its more popular variants (e.g., Munos, 2007; Farahmand et al., 2010). That said, (1) hardness results exist under a weaker form of the assumption (see Appendix A.2), and (2) whenever the transition dynamics admit low-rank stochastic factorization, there always exist data distributions that yield small $C_{\mathcal{S}}$ despite that $|\mathcal{S}|$ can be arbitrarily large; see Appendix A.1, where we also discuss how Assumption 1 compares to no inherent Bellman errors in the context of low-rank MDPs. We investigate why it is difficult to work with more relaxed assumptions in Section 7.2, and discuss how to mitigate the negative consequences when the assumption is violated in Appendix D.

A direct consequence of Assumption 1, which we will use later to control error propagation and distribution shift, is the following proposition.

Let $\nu$ be a distribution over $\mathcal{S}\times\mathcal{A}$ and $\pi$ be a policy. Let $\nu^{\prime}=P(\nu)\times\pi$ denote the distribution specified by the generative process $(s^{\prime},a^{\prime})\sim\nu^{\prime}\Leftrightarrow(s,a)\sim\nu,s^{\prime}\sim P(\cdot|s,a),a^{\prime}=\pi(s^{\prime})$. Under Assumption 1, we have $\|\nu^{\prime}/\mu\|_{\infty}:=\max_{s,a}\nu^{\prime}(s,a)/\mu(s,a)\leq C$. Also note that $\|(d_{0}\times\pi)/\mu\|_{\infty}\leq C$.

3 Value-function Approximation

Since the state space $\mathcal{S}$ can be prohibitively large, function approximation is necessary for scaling RL to large and complex problems. In the value-function approximation setting, we are given a function class $\mathcal{F}\subset(\mathcal{S}\times\mathcal{A}\to[0,V_{\max}])$ to model $Q^{\star}$. Unlike prior works that measure the approximation error of $\mathcal{F}$ using inherent Bellman errors (Munos, 2007; Antos et al., 2008)—which amounts to assuming that $\mathcal{F}$ is (approximately) closed under $\mathcal{T}$—we will measure the error using Definition 1, where error only implies realizability, $Q^{\star}\in\mathcal{F}$. In fact, given that the assumptions required by all existing algorithms are substantially stronger than realizability, Chen & Jiang (2019, Conjecture 8) conjecture that polynomial sample complexity is unattainable in batch RL when we only impose realizability on $\mathcal{F}$, which is why our result may be surprising.

4 Polynomial Learning

Our goal is to devise a statistically efficient algorithm with the following kind of guarantee: with high probability we can learn an $\epsilon$-optimal policy $\hat{\pi}$, that is, $J(\hat{\pi})\geq J(\pi^{\star})-\epsilon\cdot V_{\max}$, when $\mathcal{F}$ is realizable and the dataset $D$ is only polynomially large. The polynomial may depend on the effective horizon $1/(1-\gamma)$, the statistical complexity of the function class $\log|\mathcal{F}|$, the concentrability coefficient $C$, (the inverse of) the suboptimality gap $\epsilon$, and $1/\delta$ where $\delta$ is the failure probability. Our results can also accommodate the more general setting when $\mathcal{F}$ is not exactly realizable, in which case the suboptimality of $\hat{\pi}$ is allowed to contain an additional term proportional to the approximation error $\epsilon_{\mathcal{F}}$ up to a polynomial multiplicative factor.

Algorithm and the Guarantee

In this section, we introduce and provide intuitions for our algorithm, and state its sample complexity guarantee which will be proved in the subsequent sections.

While realizability is the only expressivity condition assumed, being piecewise constant is a major structural assumption, and is too restrictive to accommodate practical function-approximation schemes such as linear predictors or neural networks, let alone the completely unstructured set of functions one would encounter in model selection (Section 7.1). How can we make use of this observation?

An immediate idea is improper learning, i.e., augmenting $\mathcal{F}$—which is not piecewise constant in general and may have an arbitrary structure—to its smallest superset that is piecewise constant, which automatically inherits realizability from $\mathcal{F}$. To do so, we may first discretize the output of each function $f\in\mathcal{F}$ up to a small discretization error $\epsilon_{\text{dct}}$,When $V_{\max}/\epsilon_{\text{dct}}$ is an odd integer, discretization onto a regular grid $\{\epsilon_{\text{dct}},3\epsilon_{\text{dct}},\ldots,V_{\max}-\epsilon_{\text{dct}}\}$ guarantees at most $\epsilon_{\text{dct}}$ approximation error, and the cardinality of the set is $V_{\max}/2\epsilon_{\text{dct}}$. For arbitrary $\epsilon_{\text{dct}}\in(0,V_{\max})$, a similar discretization yields a cardinality of $\lceil V_{\max}/2\epsilon_{\text{dct}}\rceil$, and we upper-bound it by $V_{\max}/\epsilon_{\text{dct}}$ throughout the analysis for convenience. and partition $\mathcal{S}\times\mathcal{A}$ by grouping state-action pairs together only when the output $f\in\mathcal{F}$ (after discretization) is constant across them. The problem is that, the resulting function class is way too large compared to $\mathcal{F}$; its statistical complexity—measured by the number of groups—can be as large as $(V_{\max}/\epsilon_{\text{dct}})^{|\mathcal{F}|}$, doubly exponential in $\text{poly}\log|\mathcal{F}|$ which is what we can afford!

To turn this idea into a polynomial algorithm, we note that the statistical complexity of the superset is affordable when $|\mathcal{F}|$ is constant, say, $|\mathcal{F}|=2$. This provides us with a procedure that identifies $Q^{\star}$ out of two candidate functions. To handle an exponentially large $\mathcal{F}$, we simply perform pairwise comparisons between all pairs of $f,f^{\prime}\in\mathcal{F}$, and output the function that has survived all pairwise comparisons involving it. Careful readers may wonder what happens when $Q^{\star}\notin\{f,f^{\prime}\}$, as realizability is obviously violated. As we will show in Section 6, the outcomes of these “bad” comparisons simply do not matter: $Q^{\star}$ is never involved in such comparisons, and any other function $f$ will always be checked against $f^{\prime}=Q^{\star}$, which is enough to expose the deficiency of a bad $f$.

The above reasoning ignores approximation and estimation errors, which we handle in the actual algorithm and its analysis; see Algorithm 1. Below we state its sample complexity guarantee, which is the main theorem of this paper.

Under Assumption 1, with probability at least $1-\delta$, BVFT (Algorithm 1) with $\epsilon_{\text{dct}}=\frac{(1-\gamma)^{2}\epsilon V_{\max}}{16\sqrt{C}}$ returns a policy $\hat{\pi}$ that satisfies

The most outstanding characteristic of the sample complexity is the $1/\epsilon^{4}$ rate. In fact, the poor dependencies on $C$ and $1/(1-\gamma)$ are both due to $1/\epsilon^{4}$: when we rewrite the guarantee in terms of suboptimality gap as a function of $n=|D|$, we see an $O(\sqrt{C}n^{-1/4}/(1-\gamma)^{2})$ estimation-error term, featuring the standard $\sqrt{C}$ penalty due to distribution shift and quadratic-in-horizon error propagation.

The $1/\epsilon^{4}$ rate comes from two sources: $1/\epsilon^{2}$ of it is due to the worst-case statistical complexity of the piecewise constant classes created during pairwise comparisons. The other $1/\epsilon^{2}$ is the standard statistical rate. While standard, proving $O(1/\epsilon^{2})$ concentration bounds in our analysis turns out to be technically challenging and requires some clever tricks. We refer mathematically inclined readers to Section 5.2.3 for how we overcome those challenges.

We prove Theorem 2 in the next two sections. Section 5 establishes the essential properties of the pairwise comparison step in Line 8, where we view the problem at a somewhat abstract level to attain proof modularity. Section 6 uses the results in Section 5 to prove the final guarantee.

Value-function Validation using a Piecewise Constant Function Class

In this section we analyze a subproblem that is crucial to our algorithm: given a piecewise constant class $\mathcal{G}_{\phi}\subset(\mathcal{S}\times\mathcal{A}\to[0,V_{\max}])$ (induced by $\phi$, a partition of $\mathcal{S}\times\mathcal{A}$)We treat $\phi$ as mapping $\mathcal{S}\times\mathcal{A}$ to an arbitrary finite codomain, and $g(s,a)=g(s^{\prime},a^{\prime})~{}\forall g\in\mathcal{G}_{\phi}$ iff $\phi(s,a)=\phi(s^{\prime},a^{\prime})$. with small realizability error $\epsilon_{\phi}:=\epsilon_{\mathcal{G}_{\phi}}$, we show that we can compute a statistic for any given function $f_{0}:\mathcal{S}\times\mathcal{A}\to[0,V_{\max}]$, and the statistic will be a good surrogate for $\|f_{0}-Q^{\star}\|$ as long as Assumption 1 holds and the sample size is polynomially large. We use $|\phi|$ to denote the number of equivalence classes induced by $\phi$.

As Section 4 and Algorithm 1 have already alluded to, later we will invoke this result when comparing two candidate value functions $f$ and $f^{\prime}$ (with $f_{0}=f$), and define $\phi$ as the coarsest partition that can express both $f$ and $f^{\prime}$; when $Q^{\star}\in\{f,f^{\prime}\}$, $\epsilon_{\phi}$ will be small. To maintain the modularity of the analysis, however, we will view $\phi$ as an arbitrary partition of $\mathcal{S}\times\mathcal{A}$ in this section.

The statistic we compute is $\|f_{0}-\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}\|_{2,D}$ (c.f. Line 8 of Algorithm 1), where $\widehat{\mathcal{T}}_{\phi}^{\mu}$ is defined as follows:

Define $\widehat{\mathcal{T}}_{\phi}^{\mu}$ as the sample-based projected Bellman update operator associated with $\mathcal{G}_{\phi}$: for any $f:\mathcal{S}\times\mathcal{A}\to[0,V_{\max}]$, $\widehat{\mathcal{T}}_{\phi}^{\mu}f:=$

To develop intuitions, we first consider the special case of $|D|\to\infty$ and $\epsilon_{\phi}=0$. In this scenario, we can show that $Q^{\star}$ is the unique fixed point of $\widehat{\mathcal{T}}_{\phi}^{\mu}$, which justifies using $\|f_{0}-\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}\|$ as a surrogate for $\|f_{0}-Q^{\star}\|$. The concepts and lemmas introduced here will also be useful for the later analysis of the general case.

We start by defining $\mathcal{T}_{\phi}^{\mu}$ as $\widehat{\mathcal{T}}_{\phi}^{\mu}$ when $|D|\to\infty$.

Define $\mathcal{T}_{\phi}^{\mu}$ as the projected Bellman update where the projection is onto $\mathcal{G}_{\phi}$, weighted by $\mu$. That is, for any $f:\mathcal{S}\times\mathcal{A}\to[0,V_{\max}]$,

Next, we show that it is possible to define an MDP $M_{\phi}$, such that $\mathcal{T}_{\phi}^{\mu}$ coincides with the Bellman update of $M_{\phi}$. Readers familiar with state abstractions may find the definition unusual, as the “abstract MDP” associated with $\phi$ is typically defined over the compressed (or abstract) state space instead of the original one (e.g., Ravindran & Barto, 2004). We define $M_{\phi}$ over $\mathcal{S}$ because (1) our $\phi$ is an arbitrary partition of $\mathcal{S}\times\mathcal{A}$, which does not necessarily induce a consistent notion of abstract states, and (2) even when it does, the MDPs defined over $\mathcal{S}$ are dual representations to and share many important properties with the classical notion of abstract MDPs (Jiang, 2018).

Define $M_{\phi}=(\mathcal{S},\mathcal{A},P_{\phi},R_{\phi},\gamma,d_{0})$, where

$\mathcal{T}_{\phi}^{\mu}$ is the Bellman update operator of $M_{\phi}$.

When $\epsilon_{\phi}=0$, $Q^{\star}$ is the unique fixed point of $\mathcal{T}_{\phi}^{\mu}$.

2 The General Case

In the general case, we want to show that $\|f_{0}-\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}\|_{2,D}$ and $\|f_{0}-Q^{\star}\|$ control each other. The central result of this section is the following proposition:

Then, with probability at least $1-\delta$, for any $\nu\in\Delta(\mathcal{S}\times\mathcal{A})$ such that $\|\nu/\mu\|_{\infty}\leq C$,

Proving the proposition requires quite some preparations. We group the helper lemmas according to their nature in Sections 5.2.1 to 5.2.3, and prove Proposition 5 in Section 5.2.4.

The first two lemmas allow us to characterize error propagation in later proofs. That is, it will help answer the question: if we find $\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}$ to be small (but nonzero), why does it imply that $\|f_{0}-Q^{\star}\|$ is small?

In fact, it is precisely this analysis that demands the strong definition of concentrability coefficient $C_{\mathcal{S}}$ in Assumption 1: as we will later show in the proof of Proposition 5 (Section 5.2.4), the error propagates according to the dynamics of $M_{\phi}$ instead of that of $M$ (c.f. the $P_{\phi}(\nu)$ term in Eq.(45)). Therefore, popular definitions of concentrability coefficient (e.g., Munos, 2007; Antos et al., 2008; Farahmand et al., 2010; Xie & Jiang, 2020)—which all consider state distributions induced in $M$—do not fit our analysis. Fortunately, the $C_{\mathcal{S}}$ defined in Assumption 1 has a very nice property, that it automatically carries over to $M_{\phi}$ no matter what $\phi$ is:

Any $C<\infty$ that satisfies Assumption 1 for the true MDP $M$ also satisfies the same assumption in $M_{\phi}$. As a further consequence, Proposition 1 is also satisfied when $P$ is replaced by $P_{\phi}$.

The next lemma parallels Proposition 4 in Section 5.1, where we showed that $\|Q^{\star}-\mathcal{T}_{\phi}^{\mu}Q^{\star}\|=0$ when $\epsilon_{\phi}=0$. When $\epsilon_{\phi}$ is non-zero, we need a more robust version of this result showing that $\|Q^{\star}-\mathcal{T}_{\phi}^{\mu}Q^{\star}\|$ is controlled by $\epsilon_{\phi}$.

$\|Q^{\star}-\mathcal{T}_{\phi}^{\mu}Q^{\star}\|_{\infty}\leq 2\epsilon_{\phi}$.

2.3 Concentration Bounds

We need two concentration events: that $\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}$ is close to $\mathcal{T}_{\phi}^{\mu}f_{0}$, and that $\|f_{0}-\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}\|_{2,D}$ is close to $\|f_{0}-\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}\|_{2,\mu}$. We will split the failure probability $\delta$ evenly between these events.

We begin with the former, which requires a standard result for realizable least-square regression. The proof is deferred to Appendix B.5.

We then use Lemma 8 to prove that $\|\widehat{\mathcal{T}}_{\phi}^{\mu}f-\mathcal{T}_{\phi}^{\mu}f\|_{2,\mu}$ is small.

The key proof idea is to leverage a special property of piecewise constant classesAn alternative (and much messier) approach is to prove scalar-valued concentration bounds for $\widehat{\mathcal{T}}_{\phi}^{\mu}f$ in each group of state-action pairs. Those groups with few data points will have high uncertainty, but they also contribute little to $\|\cdot\|_{2,\mu}$. Compared to this approach, our proof is much simpler. to reduce the analysis to the realizable case: regressing $(s,a)\mapsto r+\gamma V_{g}(s^{\prime})$ over $\mathcal{G}_{\phi}$ is equivalent to regressing $x\mapsto r+\gamma V_{g}(s^{\prime})$ (with $x=\phi(s,a)$) over a “tabular” function class, where the $s,a|x$ portion of the data generation process is treated as part of the inherent label noise. After switching to this alternative view, the tabular class over the codomain of $\phi$ is fully expressive and always realizable, which makes Lemma 8 applicable. See Appendix B.6 for the full proof of Lemma 9.

The second concentration result we need is an upper bound on $|\|f_{0}-g\|_{2,D}-\|f_{0}-g\|_{2,\mu}|$ for all $g\in\mathcal{G}_{\phi}$ simultaneously. We need to union bound over $g\in\mathcal{G}_{\phi}$ because our statistic is $\|f_{0}-g\|_{2,D}$ with $g=\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}$, which is a data-dependent function.

W.p. $\geq 1-\delta/2$, $\forall g\in\mathcal{G}_{\phi}$, $|\|f_{0}-g\|_{2,D}-\|f_{0}-g\|_{2,\mu}|\leq\epsilon_{1}$, as long as

It is straightforward to bound $|\|f_{0}-g\|_{2,D}^{2}-\|f_{0}-g\|_{2,\mu}^{2}|$ (note the squares), but a naïve conversion to a bound on the desired quantity (difference without squares) would result in $O(n^{-1/4})$ rate. To obtain $O(n^{-1/2})$ rate, we consider two situations separately, depending on whether $\|f_{0}-g\|_{2,\mu}$ is below or above certain threshold: when it is below the threshold, we can use Bernstein’s to exploit the low variance of $(f_{0}-g)^{2}$; when it is above the threshold, we obtain the bound by factoring the difference of squares. Combining these two cases with an $O(\epsilon_{1})$ threshold yields a clean $O(n^{-1/2})$ result; see proof details in Appendix B.7.

2.4 Proof of Proposition 5

We are now ready to prove Proposition 5. Due to space limit we only provide a proof sketch in the main text.

To prove Eq.(6), define $\pi_{f,f^{\prime}}$ as the policy $s\mapsto\operatorname*{arg\,max}_{a}\max\{f(s,a),f^{\prime}(s,a)\}$. Consider any $\nu$ such that $\|\nu/\mu\|_{\infty}\leq C$, we have $\|Q^{\star}-f_{0}\|_{2,\nu}\leq$

The first term can be bounded via Lemma 7. The second term is bounded by $\gamma\|Q^{\star}-f_{0}\|_{2,P_{\phi}(\nu)\times\pi_{\hat{f},Q^{\star}}}$, where $P_{\phi}(\nu)\times\pi_{\hat{f},Q^{\star}}$ is a distribution that also satisfies $\|(\cdot)/\mu\|_{\infty}\leq C$ (Proposition 1) and hence can be handled by recursion. The third can be bounded by $\sqrt{C}\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}$ due to $\|\nu/\mu\|_{\infty}\leq C$, and $\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}$ can be related to $\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}$ by the concentration bounds established in Section 5.2.3, which are satisfied due to the choice of $|D|$ in the proposition statement.

To prove Eq.(7), we can similarly relate $\|f_{0}-\widehat{\mathcal{T}}_{\phi}^{\mu}f_{0}\|_{2,D}$ to $\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}$ via the concentration bounds, and

Proof of Theorem 2

With the careful analysis of the pairwise-comparison step given in Section 5, we are now ready to analyze Algorithm 1. Roughly speaking, we will make the following arguments:

For the output $\hat{f}$, if $\max_{f^{\prime}}\mathcal{E}(\hat{f};f^{\prime})$ is small, then $\hat{f}\approx Q^{\star}$. (Eq.(6) of Proposition 5)

That $\max_{f^{\prime}}\mathcal{E}(\hat{f};f^{\prime})$ will be small, because $\max_{f^{\prime}}\mathcal{E}(f^{\star};f^{\prime})$ is small, where $f^{\star}\in\mathcal{F}$ is the best approximation of $Q^{\star}$ in Definition 1. (Eq.(7) of Proposition 5)

Before we delve into the proof of Theorem 2, we need yet another lemma, which connects $\epsilon_{\phi}$ in Section 5 to the approximation error of $\mathcal{F}$. As Section 4 has suggested, this is feasible because we are only concerned with the comparisons involving $f^{\star}$, and $\epsilon_{\phi}$ may be arbitrarily large otherwise.

The $\phi$ induced from Line 7 satisfies $|\phi|\leq(V_{\max}/\epsilon_{\text{dct}})^{2}$. When $f^{\star}\in\{f,f^{\prime}\}$, we further have $\epsilon_{\phi}\leq\epsilon_{\mathcal{F}}+\epsilon_{\text{dct}}$.

Let $\phi$ be the partition induced by $\hat{f}$ and $f^{\star}$. According to Eq.(6), for any $\nu$ s.t. $\|\nu/\mu\|_{\infty}\leq C$,

It then remains to bound $\max_{f^{\prime}}\mathcal{E}(\hat{f};f^{\prime})$. Note that

For any $f^{\prime}$, let $\phi^{\prime}$ be the partition of $\mathcal{S}\times\mathcal{A}$ induced by $f^{\star}$ and $f^{\prime}$. Then

Combining the above results, we have for any $\nu$ s.t. $\|\nu/\mu\|_{\infty}\leq C$,

Finally, since any state-action distribution induced by any (potentially non-stationary) policy always satisfies Proposition 5, by Chen & Jiang (2019, Lemma 13) we have

Discussions and Conclusions

When learning $Q^{\star}$ from a batch dataset in practice, one would like to try different algorithms, different function approximators, and even different hyperparameters for a fixed algorithm and see which combination gives the best result, as is always the case in machine-learning practices. In supervised learning, this can be done by a simple cross-validation procedure on the holdout dataset. In batch RL, however, how to perform such a model-selection step in a provably manner has been a widely open problem.See Mandel et al. (2014) and Paine et al. (2020) for empirical advances on this problem.

In comparison, BVFT provides a more direct approach with a much stronger guarantee: let $Q_{1},\ldots,Q_{m}$ be the output of different base algorithms. We can simply run BVFT on the holdout dataset with $\mathcal{F}=\{Q_{i}\}_{i=1}^{m}$. The only function-approximation assumption we need is that one of $Q_{i}$’s is a good approximation of $Q^{\star}$, which is hardly an assumption as there is little we can do if all the base algorithms produce bad results. Compared to prior works, our approach is much more agnostic w.r.t. the details of the base algorithms, our loss and guarantees are directly related to $\|f-Q^{\star}\|$ as opposed to relying on (possibly loose) upper bounds based on bisimulation, and our statistical guarantee scales to an exponentially large $\mathcal{F}$ as opposed to a constant-sized one.

Another common approach to model selection is to estimate $J(\pi)$ for each candidate $\pi$ via off-policy evaluation (OPE).As a side note, BVFT can be adapted to OPE when $Q^{\pi}\in\mathcal{F}$ for target policy $\pi$ as long as we change the $\max$ operator in $\widehat{\mathcal{T}}_{\phi}^{\mu}$ to $\pi$, though Assumption 1 will still be needed. OPE-based model selection has very different characteristics compared to BVFT, and they may be used together to complement each other; see a more detailed comparison and discussion in Appendix F.

2 On the Assumption of Exploratory Data

As noted in Section 3.2, our Assumption 1 adopts a relatively stringent definition of concentrability coefficient. A more standard definition is the following, as appeared in the hardness conjecture of Chen & Jiang (2019):

Let $d^{\pi}_{t}$ be the distribution of $(s_{t},a_{t})$ when we start from $s_{0}\sim d_{0}$ and follow policy $\pi$, which we will call an admissible distribution. We assume that there exists $C<\infty$ such that $\|d_{t}^{\pi}/\mu\|_{\infty}\leq C$ for any (possibly nonstationary) policy $\pi$ and $t\geq 0$.

In Appendix C we construct 3 scenarios to illustrate the difficulties (and sometimes possibilities) in extending our algorithm and its guarantees to a weaker data assumption such as Assumption 2; due to space limit we only include a high-level summary of the results below. In the first construction, we show that BVFT fails under Assumption 2 in a very simple MDP if we are allowed to provide a contrived $\mu$ distribution to the learner where data is unnaturally missing in certain states (Figure 1). Motivated by the unnaturalness of the construction, we attempt to circumvent the hardness by imposing an additional mild assumption on top of Assumption 2, that $\mu$ must itself be “admissible” . While it becomes much more difficult to construct a counterexample against the algorithm, it is still possible to design a scenario where our analysis breaks down seriously (Figure 2). We conclude with a positive result showing that the actual assumption we need is somewhere in between Assumptions 1 and 2, for that our algorithm and analysis work for a simple and natural “on-policy” case which obviously violates Assumption 1; formulating a tighter version of the assumption in a natural and interpretable manner remains future work.

3 Conclusions

We conclude the paper with a few open problems:

Is it possible to circumvent the failure modes discussed in Section 7.2 with novel algorithmic ideas, so that a variant of BVFT only requires a weaker assumption on data? On a related note, the original hardness conjecture of Chen & Jiang (2019) remains unsolved: our positive result assumes a stronger data assumption, and the negative results of Wang et al. (2020); Amortila et al. (2020) assume weaker ones.

When the data is seriously under-exploratory, to the extent that it is impossible to compete with $\pi^{\star}$ (Fujimoto et al., 2019; Liu et al., 2019, 2020), what is the minimal function-approximation assumption that enables polynomial learning? In particular, requiring that $\mathcal{F}$ realizes $Q^{\star}$ no longer makes sense as we do not even attempt to compete with $\pi^{\star}$. Recent works often suggest that we compete with $\pi$ whose occupancy is covered by $\mu$, but as of now very strong expressivity assumptions are needed to achieve such an ambitious goal (e.g., Jiang & Huang, 2020, Proposition 9). It will be interesting to explore more humble objectives and see if the algorithmic and analytical ideas in this work extend to the more realistic setting of learning with non-exploratory data.

Acknowledgments

The authors thank Akshay Krishnamurthy, Yu Bai, Yu-Xiang Wang for discussions related to Lemma 10, and Alekh Agarwal for numerous comments and discussions after the initial draft of the paper was released. Nan Jiang acknowledges support from the DEVCOM Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196 (ARL IoBT CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

References

Appendix A Further Discussions of Assumption 1

Here we show that in general environments whose transition admits low-rank stochastic factorization, there always exists $\mu$ that satisfies Assumption 1 with a small $C$.

$C_{\mathcal{A}}\leq|\mathcal{A}|$ follows from the uniformity of $\mu(a|s)$. For $C_{\mathcal{S}}\leq d$, note that $P(\cdot|s,a)$ and $d_{0}(\cdot)$ are convex combinations of rows of $P_{2}$, and $\mu(s)$ is designed to be uniform mixture of these rows, so $P(s^{\prime}|s,a)/\mu(s^{\prime})$ is always bounded by the number of rows, which is $d$. ∎

Comparison to Standard Concentrability The more lenient and popular definitions of concentrability (e.g., Assumption 2) are also found to be satisfiable in low-rank MDPs—in fact, such low-rankness is the only type of general structure known to enable concentrability (Chen & Jiang, 2019, Proposition 10). Comparing our Example 1 with the example given by Chen & Jiang (2019), the most outstanding difference is that in their case, the data distribution $\mu$ can be a mixture of state distributions induced by different policies in the environment; if a hidden factor cannot be reached by any policy, it is possible that any mixture distribution may fail to satisfy Assumption 1 with a reasonably small $C$.

Comparison to No Inherent Bellman Errors In the above low-rank MDP scenario, the assumption that $\mathcal{F}$ has no inherent Bellman error (Antos et al., 2008; Chen & Jiang, 2019)—which enables polynomial sample complexity for many existing algorithms—can provably hold when the left factorization matrix (the analogy of $P_{1}$ in Example 1) is known to the learner as state-action features, so it is worth comparing such a setting to ours. In this setting, which is often known as linear MDPs (Jin et al., 2020), one can choose $\mathcal{F}$ to be the linear class induced by the left factorization matrix, which is guaranteed to be closed under $\mathcal{T}$, i.e., have no inherent Bellman errors. In contrast, our Assumption 1 holds without relying on knowing the left factorization matrix. The price we pay is that we require a stochastic factorization (Example 1) instead of just low-rankness, and whether Algorithm 1 can hold with just low-rankness (possibly with additional mild assumptions) is an open problem.

A.2 Lower bounds

We assume that there exists $C<\infty$, such that for any $f,f^{\prime}\in\mathcal{F}$, $\|f-f^{\prime}\|_{2,d_{t}^{\pi}}^{2}\leq C\|f-f^{\prime}\|_{2,\mu}^{2}$ for any (possibly nonstationary) policy $\pi$ and $t\geq 0$ (see Assumption 2 for the definition of $d_{t}^{\pi}$).

In the setup of our main text, if we replace Assumption 1 with Assumption 3, no algorithm with finite sample complexity exists.

Next we consider the relationship between Assumptions 1, 2, and 3 in the following result; the proof is elementary and can be extracted from existing analyses (Munos, 2003, 2007; Chen & Jiang, 2019).

Assumption 1 $\Rightarrow$ Assumption 2 $\Rightarrow$ Assumption 3.

With these results, we now can relate the lower bounds Wang et al. (2020); Amortila et al. (2020) to our positive result: indeed they do not contradict each other, as the negative results use the weakest form of concentrability (the $\mathcal{F}$-aware version in Assumption 3), and our positive result uses the strongest form (Assumption 1). Furthermore, to circumvent the hardness in Proposition 12, imposing linear structure on $\mathcal{F}$—which is a very strong structural assumption—does not help, as the hardness results of Wang et al. (2020); Amortila et al. (2020) still apply. On the other hand, making a stronger data assumption as in Assumption 1 would avoid the lower bound.

As a final remark, the hardness conjecture of Chen & Jiang (2019), which uses Assumption 2, remains unsolved. Originally Chen & Jiang (2019) argued that hardness conjecture is highly likely true given the lack of positive results under realizability, but given our work the picture is much less clear now. If we still anticipate a hardness result, our work has substantially narrowed the search space for the lower-bound constructions (if they exist): we will necessarily be able to establish the lower bound with either $|\mathcal{F}|=2$ or $\mathcal{F}$ being piecewise constant, otherwise our tournament procedure can extend the polynomial upper bounds for these special settings to arbitrary function classes.

Appendix B Proofs

B.2 Proof of Proposition 4

The existence and the uniqueness of the fixed point of $\mathcal{T}_{\phi}^{\mu}$ follow from Lemma 3, so it suffices to check $Q^{\star}=\mathcal{T}_{\phi}^{\mu}Q^{\star}$. For any $(s,a)$, we will calculate $(\mathcal{T}_{\phi}^{\mu}Q^{\star})(s,a)$ using Eq.(12), which is a convex average of terms in the form of

B.3 Proof of Lemma 6

B.4 Proof of Lemma 7

Let $g^{\star}=\operatorname*{arg\,min}_{g\in\mathcal{G}_{\phi}}\|g-Q^{\star}\|_{\infty}$, and $\|g^{\star}-Q^{\star}\|_{\infty}=\epsilon_{\phi}$. For any $(s,a)$,

B.5 Proof of Lemma 8

Applying the one-sided Bernstein and union bounding over all $h^{\prime}\in\mathcal{H}^{\prime}$: w.p. $1-\delta$, $\forall h^{\prime}\in H^{\prime}$,

Now for any $h\in\mathcal{H}$, let $h^{\prime}$ be its closest function in $\mathcal{H}^{\prime}$, and

We have already bounded the first term, so it suffices to bound the remaining two terms. Consider

Solving for the quadratic formula, we have

B.6 Proof of Lemma 9

For any $(s,a,r,s^{\prime})$, let $x=\phi(s,a)$ and $y=r+\gamma V_{f}(s^{\prime})$. When we sample $(s,a,r,s^{\prime})$ according to the data distribution, we use $X$ and $Y$ to denote the random variables whose realizations are $x$ and $y$, respectively. Define $\mathcal{X}$ as the codomain of $\phi$, and $|\mathcal{X}|=|\phi|$. Consider the regression problem $x\mapsto y$ over function class $\mathcal{H}=[0,V_{\max}]^{\mathcal{X}}$. Let $\hat{h}$ and $h^{\star}$ be the empirical risk minimizer and the Bayes-optimal regressor, respectively, and $h^{\star}\in\mathcal{H}$ thanks to the full expressivity of $\mathcal{H}$. Also note that $\mathcal{N}_{\infty}(\mathcal{H},\epsilon_{0})\leq(V_{\max}/\epsilon_{0})^{|\mathcal{X}|}$. Invoking Lemma 8 we immediately have that w.p. $\geq 1-\delta/2$,

B.7 Proof of Lemma 10

We apply Bernstein’s inequality with a union bound over $\mathcal{G}_{\phi}^{\prime}$: w.p. $\geq 1-\delta/2$, for any $g^{\prime}\in\mathcal{G}_{\phi}^{\prime}$,

Now, for any $g\in\mathcal{G}_{\phi}$, let $g^{\prime}\in\mathcal{G}_{\phi}^{\prime}$ satisfies $\|g-g^{\prime}\|_{\infty}\leq\epsilon_{0}^{\prime}$.

Similarly, for any $g\in\mathcal{G}_{\phi}$, let $g^{\prime}\in\mathcal{G}_{\phi}^{\prime}$ satisfies $\|g-g^{\prime}\|_{\infty}\leq\epsilon_{0}^{\prime}$. Then, as long as $\|f_{0}-g\|_{2,\mu}\neq 0$,

The last line is obtained by the following argument:

where all the inequalities follow from the triangle inequality and the fact of $\|g-g^{\prime}\|_{\infty}\leq\epsilon_{0}^{\prime}$.

We now analyze the two terms above separately.

We now unify those two cases above. We first set $\epsilon_{0}^{\prime}=\epsilon_{1}/20$, and $N=\mathcal{N}_{\infty}(\mathcal{G}_{\phi},\epsilon_{0}^{\prime})\leq(V_{\max}/\epsilon_{0}^{\prime})^{|\phi|}$.

When $\|f_{0}-g\|_{2,\mu}<4\epsilon_{0}^{\prime}$, we apply the first case and obtain

for the case of $\|f_{0}-g\|_{2,\mu}<4\epsilon_{0}^{\prime}=\frac{1}{5}\epsilon_{1}$.

If $\|f_{0}-g\|_{2,\mu}\geq 4\epsilon_{0}^{\prime}$, we use the second case. The term (I) in Eq.(31) is

Since $\left|\|f_{0}-g\|_{2,D}-\|f_{0}-g\|_{2,\mu}\right|\leq\text{(I)}+\text{(II)}$, we reorder the terms and obtain

We still set $\epsilon_{0}^{\prime}=\epsilon_{1}/20$. Thus, solving

provides us with the sufficient sample size $|D|$,

Choosing the greater one between the required sample sizes for $\|f_{0}-g\|_{2,\mu}<4\epsilon_{0}^{\prime}=\epsilon_{1}/5$ and $\|f_{0}-g\|_{2,\mu}\geq 4\epsilon_{0}^{\prime}=\epsilon_{1}/5$ completes the proof. ∎

B.8 Proof of Proposition 5

Since $|D|$ in the proposition statement is chosen to satisfy the sample-size requirements in Lemmas 9 and 10, the statement of each lemma holds with probability at least $1-\delta/2$, and by union bound they hold simultaneously w.p. $\geq 1-\delta$.

Define $\pi_{f,f^{\prime}}$ as the policy $s\mapsto\operatorname*{arg\,max}_{a}\max\{f(s,a),f^{\prime}(s,a)\}$. Consider any $\nu$ such that $\|\nu/\mu\|_{\infty}\leq C$,

In Eq.(45), the first term follows from Lemma 7 and that $\|\cdot\|_{2,\nu}\leq\|\cdot\|_{\infty}$, the second from Chen & Jiang (2019, Lemmas 14 and 15), and the third from Chen & Jiang (2019, Lemma 12).

According to Lemma 6, $P_{\phi}(\nu)\times\pi_{\hat{f},Q^{\star}}$ also satisfies $\|(\cdot)/\mu\|_{\infty}\leq C$, so it can be viewed as one of those $\nu$’s we started with on the LHS, allowing us to expand the inequality indefinitely. Alternatively, we have

So for any $\nu$ such that $\|\nu/\mu\|_{\infty}\leq C$, $\|Q^{\star}-\hat{f}\|_{2,\nu}\leq\frac{2\epsilon_{\phi}+\sqrt{C}\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}}{1-\gamma}$.

It then remains to bound $\|f_{0}-\mathcal{T}_{\phi}^{\mu}f_{0}\|_{2,\mu}$:

B.9 Proof of Lemma 11

For the first claim, we may write $\phi(s,a)=(\bar{f}(s,a),\bar{f^{\prime}}(s,a))$, and the number of equivalent classes induced by $\phi$ is at most the product of the cardinalities of the codomains of $\bar{f}$ and $\bar{f^{\prime}}$, so the result follows.

For the second claim, recall that $\epsilon_{\phi}=\epsilon_{\mathcal{G}_{\phi}}=\min_{g\in\mathcal{G}_{\phi}}\|g-Q^{\star}\|_{\infty}$, so

Appendix C Obstacles in Relaxing Assumption 1

In this section we discuss the obstacles in relaxing Assumption 1. Before we start, we emphasize that the difficulties have nothing to do with the tournament procedure, and are entirely about learning $Q^{\star}$ with a realizable state-action aggregation $\phi$—a problem so standard, that the difficulties we find may have broader implications beyond the scope of this work; see Appendix C.1 for discussions on the relevance of our findings to existing RL algorithms.

We present our first counterexample in Figure 1, where Assumption 1 is violated but Assumption 2 is satisfied due to missing data in state-action pairs unreachable from the initial state $s_{0}$. A state-action aggregation $\phi$, which is guaranteed to express $Q^{\star}$, results in a projected Bellman operator $\mathcal{T}_{\phi}^{\mu}$ that has multiple fixed points other than $Q^{\star}$ even when sample size goes to infinity, and many such fixed points produce suboptimal policies. Therefore, $\|f-\mathcal{T}_{\phi}^{\mu}f\|_{2,\mu}$, which is the surrogate loss that plays a central role in our algorithm, cannot control the performance of $\pi_{f}$ in this setting; see Appendix C.1 for details.

An issue with Figure 1 is that its $\mu$ cannot be admitted in the MDP (i.e., generated by some behavior policy from $d_{0}$), and assuming admissible $\mu$ (which is reasonable) excludes this counterexample. While this may look promising, here we show that our analysis still faces substantial obstacles if we replace Assumption 1 with Assumption 2 plus admissible $\mu$. Below we explain in more details.

As Section 5.2.1 has alluded to, the error propagates according to the dynamics of $M_{\phi}$ instead of $M$ in our analysis, so the purpose of Assumption 1 is really to guarantee the following type of assumption:The actual assumption we need is slightly more complicated, that we need $\|\nu/\mu\|_{\infty}\leq C$ for any $\nu$ admissible in $M_{\phi}$ but using any other admissible $\nu^{\prime}$ from $M$ as the initial distribution. This complication, however, does not affect our counterexample. Neither does it affect the next positive result.

There exists $C<\infty$, such that for any $\phi$, we have $\|\nu/\mu\|_{\infty}\leq C$ for any $\nu$ that is admissible in $M_{\phi}$.

Unfortunately, via a carefully constructed example, we show in Figure 2 that Assumption 4 cannot be implied by Assumption 2 plus admissible $\mu$. In particular, even when Assumption 2 is satisfied with a constant $C$ and $\mu$ is admissible, we can use the aggregation to “leak” probabilities from easy-to-reach states in $\mu$ to hard-to-reach states gradually over time steps, causing an exponential blow-up of $\|\nu/\mu\|_{\infty}$. See Appendix C.2 for details.

Despite the discouraging counterexamples, we show a slightly positive result, implying that Assumption 4 could be much weaker than Assumption 1, leaving the possibility of something weaker than Assumption 1 but more natural and interpretable than Assumption 4. In particular, we show a scenario where Assumptions 2 and 4 can be satisfied with a small $C$, yet Assumption 1 may be violated badly, implying the looseness and unnecessity of Assumption 1 for our analysis.

Consider the uncontrolled case where there is only one action, and we may treat $P$ as an $|\mathcal{S}|\times|\mathcal{S}|$ transition matrix. We consider the “on-policy” case, where $d_{0}=\mu$ is an invariant distribution w.r.t. $P$, i.e., $\mu^{\top}P=\mu^{\top}$. Since an invariant distribution always exists, this does not impose any restriction on $P$, so we can make the $C$ in Assumption 1 very large: for example, when $P$ is identity, $C$ must be as large as $|\mathcal{S}|$ to satisfy Assumption 1. On the other hand, Assumption 2 is trivially satisfied with $C=1$, as $\mu$ is the only admissible distribution in $M$. Perhaps surprisingly, this is also true for Assumption 4: regardless of $\phi$, we have $\mu^{\top}P_{\phi}=\mu^{\top}P=\mu$, because $P_{\phi}$ is defined by averaging the dynamics of $P$ with weights proportional to $\mu$, and this averaging step can be ignored when the incoming distribution is $\mu$ itself.

C.1 Details of Figure 1

We construct an MDP, a data distribution $\mu$, and a realizable function class $\mathcal{F}$ with $|\mathcal{F}|=2$, such that (1) Assumption 1 is violated; (2) Assumption 2 is satisfied; (3) Algorithm 1 may output a suboptimal policy even with infinite data.

See Figure 1 for an illustration of the MDP, where the transition dynamics and the rewards are deterministic. Let $\gamma=0.9$, and $s_{0}$ be the deterministic initial state.

Let $\mu$ be uniform over all state-action pairs other than $(s_{4},a)$,The probability assigned to $(s_{3},a)$ is twice as much as that to $(s_{0},a_{1})$ by $\mu$, because the former is the abbreviation of two state-action pairs. This detail is of minor importance, and $\mu$ can be changed to many other distributions, as long as the later values of $Q$ are set in a way consistent with $\mu$. which violates Assumption 1.The fact that $\mu(s,a)>0~{}\forall s,a$ is violated is of minor concern here: we can add exponentially small probabilities to $(s_{4},a)$ in $\mu$, and with a polynomially large $D$, the non-uniqueness of the fixed point of $\widehat{\mathcal{T}}_{\phi}^{\mu}$ still persists. What is really important is that no finite $C_{\mathcal{S}}$ satisfies $P(s^{\prime}|s,a)/\mu(s^{\prime})\leq C_{\mathcal{S}}$. However, since no policy can visit $s_{3}$ or $s_{4}$ from the starting state $s_{0}$, lacking data in $s_{4}$ does not affect the validity of Assumption 2. It remains to specify $\mathcal{F}$ and show that our algorithm fails.

Our $\mathcal{F}$ consists of two functions, $Q^{\star}$ and $Q$. We specify them by writing down their values on {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(s_{0},a_{1})},(s_{0},a_{2}),(s_{1},a),(s_{2},a),{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(s_{3},a)},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(s_{4},a)} as a vector: Q^{\star}=({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1},1.9,0,1,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}) and Q=({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7},1.9,0,1,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}10}). The red and blue colors correspond to the color schemes in Figure 1 to facilitate understanding.

When we run Algorithm 1, the only nontrivial aggregation $\phi$ performs is grouping together $(s_{0},a_{1})$ and $(s_{3},a)$; $(s_{0},a_{2})$ and every other state-action pair are kept in their own equivalence classes, respectively. ($a_{1},a_{2}$ under the same state are by default aggregated except in $s_{0}$.)

Now that the construction is complete, we can verify that our loss $\|f-\mathcal{T}_{\phi}^{\mu}f\|$ is zero for both $f=Q^{\star}$ and $f=Q$. Therefore, the algorithm may choose to output the greedy policy of either function, but the greedy policy of $Q$ is suboptimal since it chooses $a_{1}$ in $s_{0}$.

This phenomenon is particularly interesting when we notice that, everything will work fine if we remove the data on $(s_{3},a)$: the algorithm will still have high uncertainty in the values of $s_{3}$ and $s_{4}$, but such uncertainty does not incorrectly propagate to $s_{0}$ and hence does not affect our ability to choose the optimal action there. Therefore, the pathological behavior is due to having data with more coverage than necessary, which may be surprising. To our best knowledge, this pathology—which affects a wide range of batch RL algorithms—is documented for the first time. It will be interesting to see if we can obtain a deeper understanding of this issue and possibly circumvent it.

C.2 Counterexample Against Admissible μ𝜇\mu

One weakness of the counterexample in Figure 1 is that $\mu$ cannot be generated by a behavior policy starting from $d_{0}$, as such admissible distributions never visit $s_{3}$. Therefore, we can exclude the pathology by assuming that $\mu$ is (a mixture) of admissible distributions, on top of Assumption 2.

In addition to Assumption 2, assume that $\mu$ is a mixture of $d_{t}^{\pi}$ for a set of $(\pi,t)$ pairs, where $\pi$ may be nonstationary and/or stochastic.

This seemingly mild additional assumption leads to some powerful corollaries. For example, any distribution induced from $\mu$ (say, with policy $\pi^{\prime}$ in $t^{\prime}$ steps) as the initial distribution (instead of $d_{0}$) will still be covered by $\mu$, since the distribution is essentially a mixture of $d_{\pi\circ\pi^{\prime}}^{t+t^{\prime}}$. Furthermore, creating a situation like Figure 1 becomes very difficult (see below for detailed reasons); in fact, we believe that it is impossible to induce hardness with a constant-depth construction as in Figure 1.

Despite the power of Assumption 5, we show below that our analysis still faces substantial obstacles even under Assumption 5. In particular, our proof around Eq.(45) requires that distribution induced in $M_{\phi}$ should also be well covered by $\mu$ (i.e., Assumption 4), and this is guaranteed by Assumption 1 via Lemma 6. If we replace Assumption 1 with Assumption 5, however, below we show in a counterexample that $M_{\phi}$ can induce a distribution that visits a state exponentially more likely compared to its likelihood in $\mu$, thus breaking Assumption 4.

See Figure 2. The true MDP $M$ is essentially a 2-armed contextual bandit, where the initial state (or context) distribution is $d_{0}(s_{t})=(1-p)p^{t-1}$ for $t$ between $1$ and a sufficiently large integer $N$ (and the rest probability goes to $s_{N+1}$; we will not need it). $0<p<1$ is a parameter to be set later. For each $s_{t}$, we will call the two actions $L$ (for “left”) and $R$ (“right”), respectively. All states other than $\{s_{t}\}$ are absorbing states. During data collection, the learner randomly starts in some $s_{t}$ according to $d_{0}$, and take actions uniformly at random. This guarantees that $C=2$ for Assumption 2. Note that we do not specify the rewards as our goal is only to show that a distribution with large density ratio against $\mu$ can be induced in $M_{\phi}$, and not to directly show the failure of the algorithm.

The dynamics of $M_{\phi}$ (Definition 4) can be equivalently described as the following: given $(s,a)$, the next-state $s^{\prime}$ is generated in two steps,

In Figure 2, we aggregate $s_{t}^{\prime}$ and $s_{t}$ together for every $t$, and the “re-drawing” step happens after the agent lands in $s_{t}^{\prime}$. That is, before the next time step, there is some probability that it will teleport to $s_{t}$. Strictly speaking we are aggregating states instead of state-action pairs, but the effects can be reproduced by e.g., adding a dummy state with only 1 action above each $s_{t}$, and aggregating this state-action pair with $(s_{t-1},R)$. We opt for a slightly different mechanism for simplicity of the construction.

We will show that with the effect of aggregation, we can induce a distribution whose density ratio against $\mu$ is exponentially large, using the policy that always takes action “$R$”. Let $P(s_{t})$ be the probability of visiting $s_{t}$ at time step $t-1$ by this policy, and let $\mu(s_{t})$ be the mass of $s_{t}$ in $\mu$. Our goal is to calculate $P(s_{t})/\mu(s_{t})$ and show that it is exponential in $t$. First, $\mu(s_{t})=p^{t-1}(1-p)/2$. The division by $2$ is because $\mu$ contains data from two different time steps ($\{s_{t}\}$ at time step , and $\{s_{t^{\prime}}\}$ and their sibling states at time step $1$). Note that the data is collected in the true MDP $M$ and the aggregation plays no role here.

Now we calculate $P(s_{t})$. The only probability path of visiting $s_{t}$ at time step $t-1$ is $s_{1}\to s_{2}^{\prime}\to s_{2}\to s_{3}^{\prime}\rightarrow s_{3}\to\ldots\to s_{t}^{\prime}\rightarrow s_{t}$. Along this path, $P(s_{1})=1-p$, and $s_{t-1}\to s_{t}^{\prime}$ is deterministic, so we focus on the probability of $s_{t}^{\prime}\to s_{t}$.

Recall from the above that whenever at $s_{t}^{\prime}$, we will redraw a state from $\{s_{t}^{\prime},s_{t}\}$ according to their probabilities in $\mu$. Therefore,

where $\mu(s_{t}^{\prime})$ is calculated based on the fact that the data collection policy is uniformly random. This gives

Therefore, when $p<1/2$, $P(s_{t})/\mu(s_{t})$ will be exponential in $t$.

Appendix D What If Assumption 1 is Violated?

When Assumption 1 is violated, the guarantees in Theorem 2 does not hold in general. However, this does not mean that the algorithm is useless or there is nothing we can do in this case. Below we discuss a few actionable items and briefly sketch the theoretical analyses that justifies them.

As Section 7.2 has shown, one possible consequence of not having Assumption 1 is that the fixed point of $\widehat{\mathcal{T}}_{\phi}^{\mu}$ may be non-unique. This suggests a diagnostic procedure that checks if such pathology occurs: let $\widehat{\mathcal{G}_{\phi}}:=\{g\in\mathcal{G}_{\phi}:\|g-\widehat{\mathcal{T}}_{\phi}^{\mu}g\|\leq\epsilon^{\prime}\}$ be the set of approximate fixed points of $\widehat{\mathcal{T}}_{\phi}^{\mu}$ where $\epsilon^{\prime}$ is some small threshold. Then, we may compute $\max_{g,g^{\prime}\in\widehat{\mathcal{G}_{\phi}}}\|g-g^{\prime}\|_{2,D}$ as a statistic for the diagnosis. If Assumption 1 is satisfied, such a maximum distance should be small as all functions in $\widehat{\mathcal{G}_{\phi}}$ should be close to the fixed point of $\mathcal{T}_{\phi}^{\mu}$ under $\|\cdot\|_{2,\mu}$, In an early stage of the project, our algorithm actually checks whether $f\in\widehat{\mathcal{G}_{\phi}}$ instead of the current Line 8. This alternative algorithm also enjoys polynomial sample complexity. and it is important to note that such a claim does not depend on $f^{\star}\in\{f,f^{\prime}\}$ (see e.g., Lemma 3). On the other hand, if the maximum distance within $\widehat{\mathcal{G}_{\phi}}$ is observed to be small when we actually run the algorithm, we can rest assured that $\|\hat{f}-Q^{\star}\|_{2,\mu}$ is small (assuming $\max_{f^{\prime}\in\mathcal{F}}\mathcal{E}(\hat{f};f^{\prime})$ is small), and we only need Assumption 2 to further guarantee the near-optimality of $\pi_{\hat{f}}$, regardless of whether Assumption 1 holds or not.

As an example, consider the counterexample in Figure 1 and Appendix C.1, where both $Q^{\star}$ and $Q$ are fixed points of $\mathcal{T}_{\phi}^{\mu}$ and $\|Q^{\star}-Q\|_{2,\mu}$ is large. As Section 7.2 suggests, the pathology goes away if we remove the data from $(s_{3},a)$. Note that $\mathcal{T}_{\phi}^{\mu}$ still has many fixed points (the value of $(s_{4},a)$ can be anything), but their distance from each other under $\|\cdot\|_{2,\mu}$ is always because $\mu$ is only supported on $s_{0},s_{1},s_{2}$, and all these fixed points induce an optimal policy from $s_{0}$.

D.2 Tweaking ϕitalic-ϕ\phi

Our main analysis treats the discretization step (Line 7) very casually. However, the structure of $\phi$ plays an important role in error propagation, and small changes in discretization can produce significantly different $\phi$’s, so one may want to search for a favorable $\phi$ among all possibilities. What should be the guideline for such a search?

Of course, there is no guarantee that we can find such a well-behaved $\phi$ for a single pair of $f,f^{\prime}$, let alone the $|\mathcal{F}|^{2}$ pairs that all need to be handled. Therefore, this suggestion is more suitable for the model-selection scenario where $|\mathcal{F}|$ is small (Section 7.1). To produce a rich set of possible $\phi$’s, one can consider various designs of the discretization grid (see Footnote 4): changing the offset of the grid, using a non-regular grid, using soft aggregations instead of hard ones, or even setting $\epsilon_{\text{dct}}$ to be slightly greater than intended. Whether it is easy to find a well-behaved $\phi$ is more of an empirical question, and we leave further investigation to future work.

It is possible to define $\epsilon_{\mathcal{F}}$ as $\inf_{f\in\mathcal{F}}\|f-Q^{\star}\|_{2,\mu}$, and still prove a polynomial sample complexity result. However, making this change leads to a suboptimal dependence on $C$ if we still follow the same proof structure. Below we briefly explain the challenges.

Appendix F Comparison to OPE in Model Selection

Section 7.1 discussed the application of BVFT to model selection. Another common approach to model selection is to estimate $J(\pi)$ for each candidate $\pi$ via off-policy evaluation (OPE). Unfortunately, unbiased OPE with importance sampling (IS) (Precup et al., 2000) incurs exponential variance in horizon when the behavior policy is significantly different from the ones being evaluated (Jiang & Li, 2016), and recent marginalized IS (MIS) methods that overcome such a “curse of horizon” require some nontrivial function-approximation assumptions. For example, even if one has a function class $\mathcal{Q}$ that realizes $Q^{\pi}$ for every $\pi$ being evaluated, the state-or-the-art approaches only provide an interval that contains $J(\pi)$ without tightness guarantees (Jiang & Huang, 2020; Feng et al., 2020), and tightness requires further assumptions on realizing marginalized importance weights (e.g., Liu et al., 2018; Uehara et al., 2020). On a related note, if a rich $\mathcal{Q}$ is used to better satisfy these additional assumptions, one has to reserve a large amount of data as holdout dataset due to the statistical complexity of $\mathcal{Q}$. In comparison, BVFT only uses function classes of a well-controlled worst-case complexity $O(1/\epsilon^{2})$.

Despite the additional assumptions, OPE has its own advantages: OPE directly estimates $J(\pi)$ instead of going through $\|f-Q^{\star}\|$ as a surrogate, and as a consequence, it removes the assumption that the base algorithms need to approximate $Q^{\star}$ and hence enjoys wider applicability. The information about $J(\pi)$ can also be valuable in certain application scenarios, which cannot be obtained by our approach (we can at the best provide an upper bound on $J(\pi^{\star})-J(\pi)$). To this end, OPE-based methods and BVFT have very different characteristics when applied to model selection, and they are complementary and may be used together to provide more information and help the practitioners in making the final decision.