1 Introduction↩︎

Model selection is a fundamental task in supervised learning and statistical learning theory. Given a sequence of model classes, the goal is to optimally balance the approximation error (bias) and estimation error (variance) offered by the potential model class choices, even though the best model class is not known in advance. Model selection algorithms are extremely well-studied in learning theory [1]–[4], and methods like cross-validation have become essential steps for practitioners.

In recent years, interest has turned to model selection in decision-making problems like bandits and reinforcement learning. A number of theoretical works have studied the online setting [5]–[11]. Similar to the bias-variance balance in supervised learning, these algorithms typically aim to select the model class with smallest statistical complexity that contains the true model. Despite these recent efforts, the current understanding of model selection in offline (or batch) reinforcement learning (RL) is comparatively nascent. Offline RL is a paradigm where the learner leverages prior datasets of logged interactions with the environment [12], [13]. The learner is tasked with returning a good policy without further environment interaction. As has been acknowledged in several recent papers [14]–[16], one of the major challenges preventing widespread deployment of offline RL algorithms in the real world is the lack of algorithmic tools for model selection, evaluation, and hyperparameter tuning. In experimental settings, researchers typically evaluate candidate learned models by using online rollouts of the policies after learning with offline data. However, such approaches are not feasible in many real world settings where the entire process of producing a single policy must be conducted only on the offline dataset, due to complications such as logistics, safety, or performance requirements. In recent years, this problem has been recognized as a major deficiency in the field and a number of efforts have been made to remedy it. On the empirical side, several researchers have proposed workflows and general heuristics specifically addressing this problem [16]–[18]. However, all have noted that solutions designed to evaluate or select models typically have their own hyperparameters and modeling choices. Consider, for example, applying off-the-shelf offline policy evaluation (OPE) methods [19], [20]. These typically require some function approximation of their own. Thus, rather than solving the problem, naively using OPE just shifts the burden of model selection to the OPE estimator. Similarly, recent efforts to solve model selection in online bandits and RL are inapplicable as they almost universally require interaction with the environment [6]–[8]. The solution to the offline problem seems to require new ideas.

On the theoretical side, there is also significant motivation for devising model selection algorithms as there is growing evidence suggesting that strong conditions on the function class² are necessary to achieve non-trivial guarantees in offline RL in the worst case [21]–[23]. Perhaps the most widely used and recognized condition is completeness [24]–[26] which essentially says that \(\mathcal{T}f \in \mathcal{F}\) for any \(f \in \mathcal{F}\), where \(\mathcal{T}\) is the Bellman operator and \(\mathcal{F}\) is the model class.³ Unsurprisingly, completeness plays an important role in the proofs of many value-based offline RL algorithms since sample efficient results are provably impossible without it (in the absence of additional assumptions – see [14], [27]). Despite the growing realization of the importance of these conditions, there seems to be comparatively little work addressing the problems of identifying complete model classes or certifying sufficient conditions for sample efficient offline RL.

[28] considered the problem of model selection in the offline setting with the intent of addressing some of the aforementioned issues. It was shown that full model selection (competitive with an oracle that has knowledge of the best model class) is impossible in general in offline reinforcement learning. They proposed several relaxations to achieve weaker oracle inequalities, but these were limited to contextual bandits with linear model classes where there is no issue of completeness. The question of whether any similar results are possible for full offline reinforcement learning with general function classes has remained open.

1.1 Contributions↩︎

1.1.0.1 Theoretical Guarantees

In this paper, we give the first rate-optimal model selection algorithm for offline RL with value function approximation. We begin by summarizing known results for a single model class using value-based methods. For any individual model class \(\mathcal{F}\) that satisfies completeness and an offline dataset of \(n\) samples with sufficient coverage, the gold-standard regret bound is \(\tilde{\mathcal{O}}\left( \sqrt{ \mathrm{\small Comp}(\mathcal{F}) /n } \right)\)⁴ where \(\mathrm{\small Comp}(\mathcal{F})\) denotes the statistical complexity of \(\mathcal{F}\). This is achieved, for example, by Fitted Q-Iteration (FQI) [26]. Clearly, one would like \(\mathrm{\small Comp}(\mathcal{F})\) be as small as possible to achieve a tighter bound.

We consider the model selection problem where we are given an offline dataset of \(n\) samples and a nested sequence of \(M\) model classes \(\mathcal{F}_1 \subseteq\ldots \subseteq\mathcal{F}_M\). We investigate the following question: Can we achieve a model selection guarantee for offline RL with regret scaling with the complexity of the smallest complete model class?

We present a novel and conceptually simple algorithm, ModBE, that achieves regret scaling with the complexity of the smallest class satisfying completeness without knowledge of this class a priori.

A guarantee of this nature is typically known as an oracle inequality since an oracle with knowledge of the "best" model class ahead of time could simply choose it. We remark that this oracle inequality is rate-optimal in \(\mathrm{\small Comp}(\mathcal{F}_{k_*})\) and \(n\), showing that we do not have to sacrifice efficiency for adaptivity. This is in contrast to some other works in model selection for decision-making where this unfortunate efficiency-adaptivity trade-off has been observed [6], [7], [14]. In Appendix 7, we discuss how the nestedness condition is necessary.

We also provide a robustness result for model selection (Theorem [thm::robust]): if no models are Bellman complete (that is, \(k_*\) does not exist), ModBE obtains \(\boldsymbol{Reg}(\hat{\pi}) \leq\tilde{\mathcal{O}}\left( \min_{k \in [M]} \sqrt{\xi_k + \mathrm{\small Comp}(\mathcal{F}_k) /n } \right)\) where \(\xi_k\) is a measure of the global completeness error of \(\mathcal{F}_k\).⁵ Our results show that, while some model selection problems remain elusive without further assumptions, strong rate-optimal oracle inequalities are still possible under standard offline RL assumptions even without knowledge of the best classes in advance.

1.1.0.2 Technical Highlights.

The key to achieving the near optimal regret rate is to achieve the near optimal excess risk rate of the squared Bellman error (which is of order \(\tilde{\mathcal{O}}\left({ \mathrm{\small Comp}(\mathcal{F}_{k_*} ) / n } \right)\)). To do this, ModBE iteratively compares the relative effectiveness of two candidate model classes by employing a hypothesis test that compares the difference of their estimated risks to a one-sided generalization bound. The fact that the test leverages only the one-sided generalization bound is crucial: using easier two-sided bounds (e.g. from uniform deviation bounds on risk estimators) leads to a squared Bellman error rate of \(\tilde{\mathcal{O}}\left( \sqrt{ \mathrm{\small Comp}( \mathcal{F}_{k_*}) / n } \right)\), which translates to a slow \(\tilde{\mathcal{O}}((\mathrm{\small Comp}( \mathcal{F}_{k_*}) / n)^{1/4})\) regret rate. Instead the one-sided generalization error allows us to ultimately obtain the optimal \(\tilde{\mathcal{O}}\left( \sqrt{ \mathrm{\small Comp}( \mathcal{F}_{k_*}) / n } \right)\) regret rate.

1.1.0.3 Practical Results.

In practice, ModBE can be instantiated with any base offline RL algorithm that attempts to minimize squared Bellman error, including but not limited to FQI. ModBE is also computationally efficient, requiring \(\mathcal{O}(H k_* M)\) calls to an empirical squared loss minimization oracle and \(\mathcal{O}(k_*)\) calls to the base offline RL algorithm. In Section 5, we demonstrate the effectiveness of ModBE on several simulated experimental domains. We use neural network-based offline RL algorithms as baselines and show that ModBE is able to reliably select a good model class.

1.2 Additional Closely Related Work↩︎

Several prior works have specifically set out to address the model selection problem from a theoretical perspective, as we do here. [28] formalized the end-to-end model selection problem for offline RL where, given nested model classes, the goal is to produce a regret bound competitive with an oracle that has knowledge of the optimal model class. Their positive results, however, were limited only to linear model classes for contextual bandits; ours apply to sequential settings. An earlier work by [29] had partially addressed our problem but made several restrictive assumptions such as a known generalization bound that underestimates the approximation error (which is generally unknown); our algorithm only relies on commonly known quantities. Another notable work is the BVFT algorithm of [14]. While initially designed for general policy optimization, BVFT can be applied to model selection [27] but it incurs a slow \(1/n^{1/4}\) regret rate in theory (compared to our \(1/n^{1/2}\)) and requires a stronger data coverage assumption. One advantage of BVFT is that it can be used more generally to tune hyperparameters beyond the selection of model classes. However, the specialization of our algorithm to model selection enables the stronger guarantees. Thus, we view the two algorithms as complementary. [30] studied abstraction selection between nested state abstractions of increasing granularity; however, this eschews problems specific to value function approximation setting. [31] studied a similar abstraction problem, giving only asymptotic guarantees. In Section 3.2, we will discuss in more detail why several seemingly natural approaches to model selection do not produce satisfactory results.

2 Preliminaries↩︎

2.0.0.1 Notation

For any \(n \in \mathbb{N}\), we let \([n] = \{1, \ldots, n\}\). The notation \(a \lesssim b\) implies that \(a \leq C b\) for some absolute constant \(C > 0\). We will use \(C, C_1, C_2 \ldots > 0\) to denote absolute constants (independent of problem parameters). For a set \(A\), \(\Delta(A)\) denotes the set of distributions over \(A\).

We consider the finite-horizon Markov decision process \(\mathcal{M}(\mathcal{X}, \mathcal{A}, H, \mathbb{P}, r, \rho)\) where \(\mathcal{X}\) is the (potentially infinite) state-space, \(\mathcal{A}\) is the action space, \(H\) is the length of the horizon, \(\mathbb{P}: \mathcal{X}\times \mathcal{A}\to \Delta(\mathcal{X})\) is the transition kernel, \(r: \mathcal{X}\times \mathcal{A}\to [0, 1]\) is a deterministic reward function, and \(\rho \in \Delta(\mathcal{X})\) is an initial state distribution. A learner interacts with the MDP by proposing an \(H\)-step policy \(\pi = ( \pi_{h})_{h \in [H]}\) where each \(\pi_h: x \mapsto \pi_h(\cdot | x)\) maps \(x \in \mathcal{X}\) to a distribution over actions in \(\Delta(\mathcal{A})\).⁶ At step \(h = 1\), \(x_1\) is drawn according to \(\rho\). Then at step \(h \in [H]\), the agent observes \(x_h\), draws \(a_h\) according to \(\pi_h(\cdot | x_h)\) observes reward \(r(x_h, a_h)\) and the MDP transitions to \(x_{h + 1}\) according to \(\mathbb{P}(\cdot | x_h, a_h)\). For a policy \(\pi\), we let \(P^\pi_h(x, a)\) and \(P^\pi_h(x)\) denote the marginal state-action and state densities of \(\pi\) respectively at step \(h\).

Following standard definitions, we let \(V_h^\pi: \mathcal{X}\to \mathbb{R}\) denote the value function of \(\pi\) at step \(h \in [H]\) which is given by \(V_h^\pi(x) = \mathbb{E}_\pi \left[ \sum_{s \geq h} r(x_s, a_s) \;\vline\;x_s = x \right].\) Here, the expectation \(\mathbb{E}_\pi\) is over trajectories under \(\pi\) with \(a_h \sim \pi_h(\cdot | x_h)\). Similarly, the action-value function \(Q^\pi_h:\mathcal{X}\times \mathcal{A}\to\mathbb{R}\) is defined as \(Q_h^\pi(x, a) = \mathbb{E}_\pi \left[ \sum_{s \geq h} r(x_s, a_s) \;\vline\;x_s = x, a_s = a \right].\) The optimal policy (which exists under mild conditions when \(H\) is finite [32]) is denoted by \(\pi^*\) and this maximizes \(V^{\pi}_h(x)\) for all \(x\) and \(h\). The average value of a policy \(\pi\) is given by \(v(\pi):= \mathbb{E}_{x \sim \rho} \left[V_1^\pi(x) \right]\). Finally, we define the Bellman operators: \(T^\pi_h Q (x, a) = r(x, a) + \mathbb{E}_{x' \sim P(\cdot | x, a), a' \sim \pi_{h + 1}(\cdot | x') } \left[ Q(x',a') \right]\) and \(T^*_h Q (x, a) = r(x, a) + \mathbb{E}_{x' \sim P(\cdot | x, a) } \left[\max_{a' \in \mathcal{A}} Q(x',a') \right].\) Note that the values of \(v(\pi)\), \(V^\pi_h\), and \(Q^\pi_{h}\) are always in \([0, H]\) due to the constraint on \(r\). For convenience, we denote the \(Q\) function of the optimal policy as \(Q^* = Q^{\pi^*}\).

We consider the setting where the learner is provided with a model class \(\mathcal{F}\subseteq(\mathcal{X}\times \mathcal{A}\to [0, H])\) to estimate action value functions at each step. For exposition, we assume this model class is finite; however, it is straightforward to extend to infinite settings with appropriate complexity measures. For simplicity, we will assume that the learner uses the same \(\mathcal{F}\) for each timestep \(h \in [H]\) but this is trivially extended. We assume that \(0 \in \mathcal{F}\) and we always write \(f_{H + 1} = 0\). For any function \(f \in \mathcal{X}\times \mathcal{A}\to [0, H]\), we define the argmax policy \(\pi_{f} (x) = \mathop{\mathrm{arg\,max}}_{a \in \mathcal{A}} f(x, a)\). We will also write \(f(x) = \max_{a \in \mathcal{A}} f(x, a)\).

2.1 Offline Reinforcement Learning↩︎

The distinguishing feature of the offline (or batch) RL is that we assume that the learner is provided with a dataset \(D\) of example transitions in the MDP. The learner itself is not permitted to interact in the environment. The objective is to produce a good policy \(\hat{\pi}\) using only data from the dataset \(D\).

Formally, the dataset decomposes as \(D = (D_h)_{h \in [H]}\) for each timestep where \(D_h = \{ ( x, a, r, x')\}\) consists of tuples of transitions and incurred rewards. We assume \(D_h\) contains \(n\) datapoints that are sampled i.i.d from a fixed marginal distribution \(\mu_h \in \Delta(\mathcal{X}\times \mathcal{A})\) and the data are independent across timesteps \(h\). That is, there are \(Hn\) datapoints total. For example, the data could be generated from \(h\)-step state-action distribution of a behavior policy \(\pi^b\) so that \(\mu_h(x,a) = P_h^{\pi^b}(x, a) = \pi^b_h(a | x ) P_h^{\pi_b}(x)\).

For \(f, g \in (\mathcal{X}\times \mathcal{A}\to \mathbb{R})\), we use the notation \(\| f- g \|_{\mu_h}^2 = \mathbb{E}_{\mu_h}\left[ ( f(x, a) - g(x, a) )^2 \right]\). The average squared Bellman error under \(\mu\) at state \(h\) with respect to \(f, g\) is \(\| f- T^*_h g \|_{\mu_h}^2\). Following classical conventions [24], [33], we make a concentrability assumption that the data distribution \(\mu\) has good coverage over the MDP for all reachable state-actions.

Concentrability is a structural assumption and it is widely regarded as perhaps the most standard assumption when studying offline RL problems [21]. We remark that recent theoretical works have striven to weaken this condition via pessimistic methods [34]–[37]. However, Theorem 2 of [28] shows that model selection bounds of this type are not possible even in contextual bandits and even though the single model class bounds are possible. As a result, we will not consider this refinement in the present paper.

In this offline setting, the learner aims to use \(D\) and \(\mathcal{F}\) to produce a policy \(\hat{\pi}\) so as to minimize the regret, which measures the difference in average value between the optimal policy \(\pi^*\) and \(\hat{\pi}\): \[\begin{align} \boldsymbol{Reg}(\hat{\pi}) := v(\pi^*) - v(\hat{\pi}). \end{align}\] The following variant of the performance difference lemma will be used throughout the paper. It shows that it is sufficient to control the squared Bellman error to bound regret.

3 Model Selection Objectives↩︎

In this section, we state our primary model selection objectives and discuss their significance as well as challenges associated with solving them.

3.1 The Model Selection Problem↩︎

For a finite function class \(\mathcal{F}\) that we consider here, the gold-standard regret guarantee for offline algorithms with value function approximation is \[\begin{align} \label{eq::single} \textstyle{ \boldsymbol{Reg}(\hat{\pi}) = \tilde{\mathcal{O}}\left( \sqrt{\mathcal{C}(\mu)\mathrm{\small Approx}(\mathcal{F}) } + \sqrt{ \mathcal{C}(\mu)\log|\mathcal{F}| \over n } \right),} \end{align}\tag{1}\] where \(\mathrm{\small Approx}(\mathcal{F}) := \max_{h \in [H], f' \in \mathcal{F}} \min_{f \in \mathcal{F}} \| f - T^*_h f' \|_{\mu}^2\) is the completeness error of the class \(\mathcal{F}\) [26]. This is achieved, for example, by the Fitted Q-Iteration (FQI) algorithm. If we were using infinite classes, we would replace \(\log |\mathcal{F}|\) with another suitable notion of complexity such as pseudodimension. Such bounds naturally exhibit a trade-off: larger function classes may have a better chance of keeping \(\mathrm{\small Approx}(\mathcal{F})\) close to zero⁷ but require more data to minimize the estimation error. Small classes face the opposite problem.

The objective of model selection is to achieve refined regret bounds that balance approximation error and estimation error. To this end, we assume that the learner is presented with not just a single model class \(\mathcal{F}\), but rather a nested sequence of \(M\) classes \(\mathcal{F}_1 \subseteq\ldots \subseteq\mathcal{F}_M\). Solving a problem with nested model classes is common practice in both supervised learning and offline RL. For example, one often starts with an extremely large class \(\mathcal{F}\) and then considers restrictions of \(\mathcal{F}\) to an increasing sequence \(\mathcal{F}_1 \subseteq\ldots \subseteq\mathcal{F}_M = \mathcal{F}\). In a linear setting, this could correspond to trying to find a subset of candidate features that are sufficient to solve the problem.

Since the approximation error is typically unknown a priori, we aim to design an algorithm capable of selecting a good class in a data-dependent manner. In particular, we would like to achieve oracle inequalities reflecting that we can compete with the performance of an oracle that has this knowledge in advance.

Our primary objective is to compete with the minimally complete model class.

Here, \(\mathcal{F}_{k_*}\) is the smallest class that satisfies completeness on the data distribution. Such oracle inequalities are common in model selection for online bandits and RL [6] – albeit they are generally not rate-optimal in that literature. In particular, Problem 1 states the regret bound should achieve the same dependence on \(\log |\mathcal{F}_{k_*}|\) and \(n\), as would an optimal offline algorithm using a single class with \(k=k_*\). In other words, we do not tolerate any worse dependence on either quantity such as \(\tilde{\mathcal{O}}(1/n^{1/4})\) rates and other lower order terms.

We are also interested in a robustness when \(k_*\) may not exist, i.e. all \(\mathcal{F}_k\) have some approximation error.

Note that \(\xi_k \geq \mathrm{\small Approx}(\mathcal{F}_k)\) by definition. For the estimation error, however, the guarantee remains rate-optimal. We remark that a solution to one of the above problems does not immediately imply a solution to the other. For example, a class \(\mathcal{F}_k\) may be complete, but \(\xi_k\) can still be large. Perhaps surprisingly, our proposed algorithm will be able to handle both problems simultaneously without knowledge of whether \(k_*\) exists, thus achieving the \(\min\) of both oracle inequalities.

3.2 Limitations of Prior Approaches↩︎

We now review some of the core challenges involved in solving the above problems. There are a number of seemingly natural approaches to model selection in RL that are surprisingly unable to produce satisfactory results, at least off-the-shelf.

3.2.0.1 Adaptive offline policy evaluation

The most natural approach, to which we have alluded in the introduction, is to first compute \(\hat{\pi}_k\) with a base algorithm using function class \(\mathcal{F}_k\), for each \(k \in [M]\). Then, one can estimate \(v(\hat{\pi}_k)\) using an off-the-shelf offline policy evaluation approach such as fitted \(Q\)-evaluation [24], [38], DICE methods [39]–[41], marginalized importance estimators [42], or doubly robust estimators [20], [43]. Then one simply picks the \(\hat{\pi}_k\) with the best estimated value. The main drawback of this approach is that nearly all of the above methods require selecting a model class to perform the estimation,⁸ and it is unclear how to balance the estimation and approximation error optimally to compete with the oracle. One possible solution is to employ the adaptive estimator of [44], which takes as inputs a sequence of offline estimators and known upper bounds on their deviations and returns an estimator that competes with the best one. This is precisely the approach taken by [28] for linear contextual bandits. However, for general function classes in RL, there is no obvious way to compute the analogous deviation bounds, which oftentimes depend on the unknown quantity \(\mathcal{C}(\mu)\). Since these bounds are required by the adaptive estimator as inputs, we are yet again left with unknown hyperparameters to tune.

3.2.0.2 Bellman error estimators

Recall we are focusing on base offline RL algorithms that attempt to minimize the squared Bellman error of objective. Therefore, one might ask whether it is possible to estimate the Bellman errors (e.g. with the validation dataset) and compare the model classes using the Bellman error as a proxy. Consider, for example, FQI which iteratively minimizes the squared Bellman error: \[\begin{align} \hat{f}_{h} = \mathop{\mathrm{arg\,min}}_{f \in \mathcal{F}_k} \hat{\mathbb{E}}_{D_h} \left[ \left( f(x, a) - r - \max_{a'} \hat{f}_{h + 1}(x', a')\right)^2 \right], \end{align}\] where we use \(\hat{\mathbb{E}}_{D_h}\) to denote the empirical mean calculated with samples from the dataset \(D_h\). Presumably, we could simply choose the model class \(\mathcal{F}_k\) that has the smallest cumulative squared error. The main issue with this approach is the classic double-sampling problem [33], [45]: the standard estimator of the Bellman error is biased, as a result of using an empirical version of the Bellman operator \(T^*\). By selecting based on this error function alone, we will end up favoring model classes that also induce low variance of the regression targets, given by \(r + \hat{f}_{h + 1}(x')\) at step \(h\). This is because the expectation is given by: \[\begin{align} \mathbb{E}_{\mu_h} \left[ \left( \hat{f}_h(x, a) - r - \hat{f}_{h + 1}(x')\right)^2 \right] & = \| \hat{f}_h - T^* \hat{f}_{h + 1} \|_{\mu_h}^2 + \mathbb{E}_{\mu_h} \left[ \mathop{\mathrm{var}}_{x' \sim \mathcal{P}(\cdot | x, a)} \left( \hat{f}_{h + 1}(x') \right) \right]. \end{align}\] In reality, we want to choose a class \(\mathcal{F}_k\) to minimize only the first term on the right-hand side, summed over \(h\in[H]\), following Lemma 1. However, the second term is generally unknown. One could assume there is a sufficiently powerful class \(\mathcal{G}\) such that \(T^*f \in \mathcal{G}\) for all \(f \in \mathcal{F}\) [46]. But there remains a question of how to select the class \(\mathcal{G}\) to trade off approximation error and estimation error, creating another unsolved model selection problem.

In the same vein, another approach we might consider is recent BVFT algorithm of [14] to select among the \(f^k\) learned by the base algorithm. This solves the model selection problem but the guarantee of BVFT has a slow \(O(1/n^{1/4})\) dependence and thus does not achieve either oracle inequality. It also, in theory, requires that a discretization parameter is set based on a concentrability coefficient stronger than \(\mathcal{C}(\mu)\), which is typically unknown. Follow up work has shown this can be chosen adaptively in practice [27].

Perhaps most conceptually related to our approach is past work which compares Bellman errors of finer-grained state abstraction functions on the Q-function computed on coarser-grain state abstraction [30]. This work provided bounds on the resulting policy performance of the selected abstraction in discrete state and action setting, where models are varying levels of state abstractions. However, this work and analysis critically depends on the discrete state and action setting: our work shows how a similar idea can be used in the value function approximation setting, with substantially different tools and analysis techniques.

Representation Learning Readers familiar with work in representation learning for RL [47] might observe that the problem vaguely resembles objectives for selecting feature representations for low rank MDPs such as [48]. Unfortunately, the problem settings are quite different, and we cannot simply adapt such representation learning algorithms to the model selection problem since they are either insensitive to the model class complexities or they require stronger realizability assumptions. It would be interesting future work to better understand the relationship between these two problems.

4 ModBE Algorithm↩︎

Having introduced the model selection objectives, we now present our main result, a novel model selection algorithm for offline RL that provably achieves the aforementioned oracle inequalities. We first give an intuitive sketch of the approach and present the full algorithm in subsequent subsection. As a thought experiment, we will consider the case when \(M = 2\) and a minimally complete class \(\mathcal{F}_{k_*}\) exists.⁹ We will also ignore logarithmic factors and \(H\) dependence for now. A key algorithmic idea is that we will first start optimistically by guessing that \(k_* = 1\). Running a base algorithm like FQI with \(\mathcal{F}_1\) on training data returns the functions \(f_1, \ldots, f_H\), which, with high probability, satisfy \[\begin{align} \textstyle{ \sum_h \| f_h - T^*_h f_{h + 1} \|_\mu^2 = \tilde{\mathcal{O}}\left( {\mathcal{C}(\mu)\log (|\mathcal{F}_1|) \over n }\right) } \end{align}\] if \(k_*\) actually equals \(1\). Given these functions, we can pose a square loss regression problem where the regression targets (i.e., the "y’s" of the regression problem) are given by the empirical Bellman updates using training data: \[\begin{align} \textstyle{ \hat{L}_h(g, f_{h + 1}) = {1 \over n} \sum_{(x, a, r, x') \in D_h} \left( g(x, a) - r - f_{h + 1}(x')\right)^2.} \end{align}\] Let \(L_h(f, g) := \mathbb{E}_{\mu_h} \left[\hat{L}_h(f, g) \right]\). Solving this regression problem for each \(h\) over the class \(\mathcal{F}_2\) will generate \(g_1, \ldots, g_H \subseteq\mathcal{F}_2\). The key insight is that the sequences \((f_h)_h\) and \((g_h)_h\) are both trying to minimize the same empirical square loss function with the same regression targets: \(r + f_{h + 1}(x')\). Unlike the Bellman error estimators from the previous section that incur biases, the losses \(L_h(f_h, f_{h + 1})\) and \(L_h(g_h, f_{h + 1})\) are comparable and estimable from a validation set. By nestedness of \(\mathcal{F}_1 \subseteq\mathcal{F}_2\), \(\mathcal{F}_2\) cannot have more approximation error on this regression problem. Provided we can get a good estimate of generalization errors \(L(f_h, f_{h + 1})\) and \(L(g_h, f_{h + 1})\) with validation data, this naturally brings forth the following generalization test: if \[\begin{align} \label{eq::gen-test} \textstyle{ L_h(g_h, f_{h + 1} ) < L(f_h, f_{h + 1}) - \tilde{\mathcal{O}}\left( {\log (|\mathcal{F}_1 |) \over n } \right) } \end{align}\tag{2}\] reject \(\mathcal{F}_1\) and pick \(\mathcal{F}_2\). Otherwise pick \(\mathcal{F}_1\). That is, a switch will occur not when \(\mathcal{F}_{2}\) performs only marginally better than \(\mathcal{F}_1\), but when it performs substantially better as measured by the generalization error that we see for both \(f_h\) and \(g_h\) on this regression problem. If 2 holds, then there is reason to believe that \(\mathcal{F}_1\) is not complete, making \(\mathcal{F}_2\) the right choice. Crucially, the test only checks for generalization error, so the tolerance term on the right side goes as \(\tilde{\mathcal{O}}\left( { \log (| \mathcal{F}_1| ) \over n } \right)\), which is the correct rate for this problem. Thus, if the test turns out to be wrong, we will only lose additive factors of the correct rate.

4.1 Full Algorithm↩︎

The full algorithm, ModBE (Model Selection via Bellman Error), is presented in Algorithm 1. While the underlying principle described just above is similar, ModBE must handle a number extensions that complicate the algorithm such as dealing with general \(M\), accounting for proper estimation errors, and being robust to the case when \(k_*\) does not exist. Interestingly, the fundamental algorithmic idea remains the same – only the tolerances change and it loops over the model classes.

ModBE takes as input a base offline RL algorithm (such as FQI), the model classes \(\mathcal{F}_1 \subseteq\ldots \subseteq\mathcal{F}_M\), and the offline dataset \(D\in [H]\). The dataset is split randomly into a training set \(D_{\text{train}}\) and a validation set \(D_{\text{valid}}\). The algorithm begins optimistically, starting with the candidate model class \(k = 1\) and running the base algorithm with \(\mathcal{F}_k\) on the training dataset to generate the candidate functions \(f\). We retrain on the empirical square loss using a class \(k'>k\) by regressing to target values \(r+f_{h+1}(x')\). This amounts to solving a sequence of \(H\) least squares regression problems using class \(k'\), yielding the functions \(g_h\).

Since \(f_h\) and \(g_h\) are attempting to solve the same regression problem (with the same target values), we can compare their performance on this shared squared loss objective \(\tilde{L}\) with validation data. We use a generalization error test in Line [line::gen-test] to decide whether to keep using class \(k\). If the test fails and it is discovered that the larger model class \(\mathcal{F}_{k'}\) is able to achieve substantially smaller loss than \(\mathcal{F}_k\), then we move to a larger model class \(k \leftarrow k + 1\). The process is repeated until all classes are exhausted or no model class \(k'\) offers a big enough improvement over \(k\) to cause the test to fail.

4.2 Rate-Optimal Oracle Inequalities↩︎

We show that this simple procedure is able to achieve both of the oracle inequalities of the previous section simultaneously. We start with a generic version of the theorem that is stated in terms of an assumed performance bound \(\omega\) on the base algorithm. We will presently instantiate the base algorithm with FQI, showing that this version precisely achieves the desired oracle inequalities with the correct rates.

In this definition, \(\beta\) represents a multiplicative factor of error on the approximation error and \(\omega\) represents the estimation error, which we expect to decrease in \(n\) and increase in the complexity of the class \(\mathcal{F}\). Generally, we will have \(\omega_{n, \delta}(\mathcal{F}) = \tilde{\mathcal{O}}\left( { \log (|\mathcal{F}| /\delta) / n }\right)\) (see Lemma [lem::fqi] for FQI). For model selection, we thus hope to achieve a bound that matches what the base algorithm would achieve had \(k_*\) been known in advance, up to additive terms of \(\sqrt{ \log | \mathcal{F}_{k_*} | \over n }\).

Our primary theorem addresses Problem 1 using an arbitrary base algorithm.

The above theorem shows a regret bound scaling with the square root of the error term \(\omega\) of the base algorithm \(\mathcal{B}\) plus a \(\tilde{\mathcal{O}}(\log(|\mathcal{F}_{k_*}|)/n)\) estimation error. Importantly, as stated in Problem 1, the statistical complexity depends only on \(\mathcal{F}_{k_*}\) and not any of the larger classes.

For concreteness, we now instantiate Theorem [thm::main] with a standard finite-horizon FQI [38] base algorithm, which satisfies Definition 2 with \(\omega_n(\mathcal{F}) = \hat{\mathcal{O}}( \log|\mathcal{F}|/n)\). This in turn translates to the desired rate-optimal oracle inequalities.

By plugging this classic result in Theorem [thm::main] as the base algorithm, we arrive at a solution to Problem 1.

The proof of Theorem [thm::main] (and by extension Corollary [cor::fqi]) follows a nearly identical intuition as outlined at the beginning of this section. In particular, the proof shows two parts: (1) ModBE will never return a value of \(k\) that exceeds \(k_*\) and (2) if ModBE returns \(k < k_*\), then the approximation error must be small because it was undetectable by the test when comparing to \(k_*\). however, a key novelty is recognizing that the generalization test in Line [line::gen-test], which compares the errors of the two model classes on the same regression problem, can be used to prove both (1) and (2).

4.2.1 Robustness↩︎

We show that the same Algorithm 1 simultaneously achieves the desired robustness result of Problem 2 when \(k_*\) does not exist without any modification.

We can use Lemma [lem::fqi] to see a solution to Problem 2 with an instantiation of FQI.

Crucially, the guarantees that solve Problems 1 and 2 are achieved simultaneously, meaning that we do not require knowledge of whether \(k_*\) exists and we can automatically get the best of both guarantees.

The proof of Theorem [thm::robust] (Corollary [cor::fqi-robust]) is more involved than that of Theorem [thm::main]. Rather than showing that the \(k\) returned by ModBE never exceeds the index attaining the minimum, we allow \(k\) to exceed it sometimes. To ensure that the error can still be bounded, we use the fact that class \((k - 1)\) must have failed the generalization test against some larger class in \([k, M]\). Using this fact, we can argue that the estimation error of the larger class can be bounded in terms of the unknown \(\xi_{k -1}\), which we know is small since \(k\) exceeds the index of the minimal class. Like before, these arguments are made possible by the generalization test in Line [line::gen-test].

4.2.1.1 Computational Complexity

ModBE is computationally efficient given a squared loss regression oracle. Within inner and outer loops over the model classes, a squared loss minimizer is computed on the training dataset and then functions are evaluated on the validation set. ModBE requires only \(\mathcal{O}(H k_*M)\) calls to the computational oracle when \(k_*\) exists (a consequence of Theorem [thm::main]) or \(\mathcal{O}(HM^2)\) in the worst case. Note that algorithms for optimizing squared loss regression problems are ubiquitous in machine learning [49].

5 Empirical Results↩︎

The previous sections outlined the strong theoretical properties of ModBE. In this section, we ask: what practical insights can be gleaned from ModBE and its theoretical guarantees? We would like to understand if the core selection method of ModBE can be applied out-of-the-box on existing offline RL algorithms with minimal effort. We evaluated ModBE in three simulated environments with discrete actions: (1) synthetic contextual bandits (CB), (2) Gym CartPole, (3) Gym MountainCar. See Appendix 10 for specific details about the setups. All training and validation sets were split 80/20.

5.0.0.1 Contextual Bandit

As a basic validation experiment, we started with the CB setting of [28] which considers a nested sequence of linear model classes with increasing dimension \(d\). Without any tuning, we simply set the tolerance of ModBE to \(\mathrm{\small Tol}(\mathcal{F}_k, \mathcal{F}_{k'}) = {d_{k'}\over n}\). Figure 2 shows the results in terms of the \(\log\)-regret as a function of the dataset size. We observe that both ModBE and Hold-Out (choosing the model class with the smallest error) are able to easily match the performance of the best model class while SLOPE [28] ends up being fooled by nearby classes.

5.0.0.2 RL Discrete Control

Our experimental setup for the RL problems in Gym [50] builds on top of the d3rlpy framework [51], which contains open-source implementations of offline RL algorithms. We used DQN [52] (which is closest to FQI). In both CartPole and MountainCar, we considered model classes that were two-layer neural networks with ReLU activations and \(d\) nodes in the hidden layer and varied the parameter \(d\). Again, we simply set the tolerance of ModBE to \(d_k/n\) motivated by pseudodimension bounds [53]. For simplicity, we modified ModBE to work in the discounted infinite horizon setting, which can trivially be done (see Appendix 10 for details on this modification). The neural network classes considered had \(d \in \{10, 50, 1000, 5000, 25000, 50000\}\). In both settings, we compared ModBE to Hold-Out, which is a seemingly sensible baseline that chooses the model class with lowest estimated Bellman error on a validation set. For deterministic settings only, this is theoretically justified. Figure 2 shows the reward as a function of the dataset size (in episodes). On CartPole, ModBE and Hold-Out are both able to compete with the best classes and are roughly at parity. However, on MountainCar, we find that Hold-Out does surprisingly poorly while ModBE is successfully able to reject the poor model classes. We conjecture that the empirical failure of Hold-out (which is not predicted in theory since the environment is deterministic) is possibly due to sensitivity to optimization error that makes the inherent Bellman error misleading. In contrast, the generalization test of ModBE seems to be more robust to this.

6 Discussion↩︎

In this paper, we introduced a new algorithm, ModBE, for model selection in offline RL: to our knowledge it is the first to achieve rate-optimal oracle inequalities in \(n\) and \(\mathrm{\small Comp}(\mathcal{F}_{k_*})\). A number of interesting open questions remain. (1) Are there rate-optimal procedures that can be used to select hyperparameters beyond model complexity such as learning rates, batch sizes, et cetera? (2) Can the ideas of ModBE be extended to more general algorithms that do not rely on Bellman error minimization? (3) For the robustness guarantee, the global completeness \(\xi\) is potentially much worse than \(\mathrm{\small Approx}(\mathcal{F})\). Is it possible to achieve a robust oracle inequality of the form \(\mathcal{O}(\min_{k} \sqrt{\mathrm{\small Approx}(\mathcal{F}_k) + { \log |\mathcal{F}_k| / n}})\) when \(k_*\) does not exist? We believe these questions are of great practical and theoretical importance for understanding how to effectively evaluate and select models in offline RL.

Checklist↩︎

1. For all authors...

   1. Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

   2. Did you describe the limitations of your work? See Introduction, Discussion, and discussions of assumptions and after every theorem statement.

   3. Did you discuss any potential negative societal impacts of your work? The work is theoretical in nature.

   4. Have you read the ethics review guidelines and ensured that your paper conforms to them?

2. If you are including theoretical results...

   1. Did you state the full set of assumptions of all theoretical results? See preliminaries and before theorem statements.

   2. Did you include complete proofs of all theoretical results? See appendix.

3. If you ran experiments...

   1. Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?

   2. Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? See Empirical Results section and Appendix 10.

   3. Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?

   4. Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? See Appendix 10.

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...

   1. If your work uses existing assets, did you cite the creators?

   2. Did you mention the license of the assets?

   3. Did you include any new assets either in the supplemental material or as a URL?

   4. Did you discuss whether and how consent was obtained from people whose data you’re using/curating?

   5. Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?

5. If you used crowdsourcing or conducted research with human subjects...

   1. Did you include the full text of instructions given to participants and screenshots, if applicable?

   2. Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable?

   3. Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation?

7 On the Nestedness of Model Classes↩︎

Throughout this work, we assume that the given model classes are nested in the sense that \(\mathcal{F}_1 \subseteq\ldots \subseteq\mathcal{F}_M\). While this is a very common problem setting in both supervised learning and reinforcement learning, it can cause theoretical issues with completeness since adding functions to a model class can actually increase in the completeness error unlike realizability-based assumptions. Despite this, the following proposition shows that no type of model selection bound is possible without this nestedness in general.

Though the argument is simple, we remark on its significance. Our model selection objectives outlined in Section 3.1 suggest that we should aim to achieve \(v(\pi^*) - \mathbb{E}\left[ v(\hat{\pi}) \right] = \tilde{\mathcal{O}}\left(\sqrt{ \mathcal{C}(\mu) \log \mathcal{F}_{k_*} \over n }\right)\) for any of the MDPs in the family, where \(n\) is the number of samples in the dataset and \(k_*\) is the index of the class that is complete for the given MDP. This is because it is guaranteed in the first condition that at least one of the classes is complete and realizes \(Q^*\).

However, the proposition shows that we will need at least \(\text{poly}(S)\) samples to achieve any non-trivial regret bound, precluding the model selection objective since \(S\) can be much larger than \(\log \mathcal{F}_{k_*}\). The proposition also ensures that \(|\mathcal{F}_i| = \Theta(1)\) (in fact the size of both in the proof is simply \(|\mathcal{F}_i| = 1\)), which is to say that the hardness is not due to the inherent complexity of the model classes.

Note that BVFT [14] does not contradict this hardness result for the same reason that it does not contradict the result of [21]: BVFT leverages a stronger coverage assumption.

8 Proof of Theorem [thm::main]↩︎

8.1 Proof Sketch↩︎

Having outlined the intuition behind the algorithm and generalization error test in Section 4, we will now sketch the proof in a simplified setting so that the primary mechanism can be seen in a slightly more formal way. We restrict the sketch to the setting where \(M = 2\) and \(k_* \in \{1, 2\}\) exists. For such a setting the definition of \(\mathrm{\small Tol}_{n}(\mathcal{F}_1, \mathcal{F}_2)\) will be excessively large, but sufficient nonetheless to prove our desired oracle inequality. We define the following quantities: \[\begin{align} L_h(f,g) & := \mathbb{E}_{\mu_h} \left( f(x, a) - r- g(x') \right)^2 \\ L_h^*(g) & := \inf_{f} L_h(f, g) \end{align}\] where the \(\inf\) in the second line is over all measurable functions. Note that this makes \(L_h^*(g)\) the irreducible error of the regression problem which is actually achieved by \(f = T^*g\). For the purposes of exposition, we will take \(n_{\text{train}}= n\) and assume that the validation error \(\tilde{L}_h(f, g)\) exactly equals its expectation \(L_h(f, g) := \mathbb{E}_{\mu_h} \left( f(x, a) - r - g(x') \right)^2\). For the sketch only, we will ignore dependence on \(H\) and we will also assume that all necessary concentration inequalities hold with high probability¹⁰. That is, the base algorithm returns functions \(f^k = (f^k_h)\) such that \[\begin{align} \label{eq::sketch-base-alg-bound} \| f^k_h - T^*_h f^k_{h + 1} \|^2_{\mu_h} \leq L \times \mathrm{\small Approx}(\mathcal{F}_k) + \omega_{n, \delta}(\mathcal{F}_k) \end{align}\tag{3}\] and the empirical minimizers \(g^2 = (g^2_h)\) in Algorithm 1 satisfy \[\begin{align} L_h(g_h^{2}, f^1_{ h +1}) - L_h^* ( f^1_{ h +1}) & \leq \tilde{\mathcal{O}}\left( \mathrm{\small Approx}(\mathcal{F}_2) + { \log |\mathcal{F}_2 | \over n } \right) \end{align}\]

We will now break the analysis down into cases:

• If it happens that \(k_* = 1\) then we will show that the test will not fail and the correct class \(k_*= 1\) will always be returned by Algorithm 1. Note that in this case \(\mathrm{\small Approx}(\mathcal{F}_1) = 0\) by definition of \(k_*\). Thus, 3 implies that for all \(h \in [H]\): \[\begin{align} L_h(f^1_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1}) = \| f^1_h - T^*_h f^1_{h +1}\|_{\mu_h}^2 & \leq \omega_{n, \delta}(\mathcal{F}_1) \end{align}\]

  Then, an algorithm that reliably picks \(k_* = 1\) should be able to tolerate generalization error on the order of at least \(\omega_{n, \delta}(\mathcal{F}_1)\). This motivates our definition of \(\mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2)\) in Line [line::tolerance] of Algorithm 1, which ensures that \(\mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2) \geq \omega_{n, \delta}(\mathcal{F}_1)\)¹¹. Then, when the algorithm reaches the generalization test in Line [line::gen-test], it will compare the error in \(L_h(f^1_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1})\) to the error in \(L_h(g^2_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1})\). Since \(\mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2) \geq \omega_{n, \delta}(\mathcal{F}_1)\) and \(L_h(f^1_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1}) \leq \omega_{n, \delta}(\mathcal{F}_1)\) (because \(k_* = 1)\), we will always have that \[\begin{align} L_h(g^2_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1}) & \geq L_h(f^1_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1}) - \mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2) \end{align}\] And, by adding \(L^*_h(f^1_{h + 1})\) to both sides of the above display, we see that the generalization test in Line [line::gen-test] will never fail: \[\begin{align} L_h(g^2_h, f^1_{h + 1}) & \geq L_h(f^1_h, f^1_{h + 1}) - \mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2) \end{align}\] meaning that Algorithm 1 will never make the switch from \(k = 1\) to \(k = 2\) when \(k_* = 1\), so the correct model class is returned and the error is then trivially bounded as \[\begin{align} \label{eq::kstar1} \| f^1_h - T^*_h f^1_{h + 1} \|_{\mu_h}^2 \leq \omega_{n, \delta} (\mathcal{F}_1) \end{align}\tag{4}\]

• If \(k_* = 2\) and the switch to \(k = 2\) is made, then the correct model class is returned and we immediately have the error bound \(\| f^2_h - T^*_h f^2_{h + 1} \|_{\mu_h}^2 \leq \omega_{n, \delta} (\mathcal{F}_2)\).

• However, if \(k_* = 2\) and the switch is not made (meaning Algorithm 1 returns \(k = 1\)), we can show that the error cannot be much worse than the error of \(k_*\). To do this, we will use the fact that the generalization test in Line [line::gen-test] has (wrongly) succeeded in order to bound the error of \(L_h(f^1_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1})\) in terms of the error of \(L_h(g^2_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1})\) plus additional terms due to the tolerance: That is, for any \(h \in [H]\) \[\begin{align} \begin{aligned}\label{eq::sketcheq1} \| f_h^1 - T^*_h f^1_{h + 1} \|_{\mu_h}^2 & = L_h(f^1_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1}) \\ & \leq L_h(g^2_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1})+ \mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2) \end{aligned} \end{align}\tag{5}\] Recall that since \(k_* = 2\), there is no approximation error for this class so \(L_h(g^2_h, f^1_{h + 1}) - L^*_h(f^1_{h + 1}) \leq \tilde{\mathcal{O}}\left( { \log |\mathcal{F}_2 | \over n} \right)\). Finally, we can apply the definition of \(\mathrm{\small Tol}_n(\mathcal{F}_1, \mathcal{F}_2)\) as well as monotonicity of \(\omega_n(\mathcal{F}_1) \leq \omega_n(\mathcal{F}_2)\) so that 5 can further be bounded as \[\begin{align} \label{eq::kstar2} \| f_h^1 - T^*_h f^1_{h + 1} \|_{\mu_h}^2 & \leq \tilde{\mathcal{O}}\left( { \log |\mathcal{F}_2 | \over n } + \omega_{n, \delta} (\mathcal{F}_2) \right) \end{align}\tag{6}\] Therefore, since \(\mathcal{F}_1\) did not fail the generalization test, we can actually use this to our advantage to say that its error is not much worse than \(\mathcal{F}_2\) even though \(k_* = 2\).

By combining the results of the case when \(k_* = 1\) (where we showed 4 holds) and the case when \(k_* = 2\) (where we showed that 6 holds), we have managed to show that the index \(k\) returned by Algorithm 1 will satisfy \[\begin{align} \| f_h^k - T^* f_{h + 1}^k \|_{\mu_h}^2 = \tilde{\mathcal{O}}\left( { \log |\mathcal{F}_{k_*} | \over n} + \omega_{n, \delta}(\mathcal{F}_{k_*} ) \right) \end{align}\] Appealing to the performance difference lemma (Lemma 1), we are able to guarantee that \[\begin{align} \boldsymbol{Reg}(\hat{\pi}) = \tilde{\mathcal{O}}\left( \sqrt{ \mathcal{C}(\mu) \left({ \log |\mathcal{F}_{k_*} | \over n} + \omega_{n, \delta}(\mathcal{F}_{k_*} ) \right) } \right) \end{align}\]

8.2 Concentration Inequalities↩︎

We now turn to the formal proof of Theorem [thm::main]. In order to make the analysis easier, we state another version of the algorithm, which is more notation-heavy but also more precise so that we can easily refer objects in the analysis at different indices. To be clear, the algorithms are identical – the notation has just been augmented to include indices and other modifiers for clarity.

We require several basic components in order for the final model selection bound to hold. The first few are concentration results concerning the datasets. These will allow us to prove generalization error bounds for each of the classes as well as to obtain good estimates of the regression error via the validation set.

Recall some useful shorthand notation to represent the true and empirical loss functions. For any measurable functions \(f, g \in (\mathcal{X}\times \mathcal{A}\to \mathbb{R})\) and a training dataset \(D = (D_h)_{h \in [H]}\) of \(n\) samples for each \(h\) and a validation dataset \(D' = (D'_h)_{h \in [H]}\) of \(m\) samples for each \(h\), we define \[\begin{align} L_h(f, g) & = \mathbb{E}_{\mu_h} \left( f(x, a) - r - g(x') \right)^2 \\ L_h^*(g) & = \inf_f L_h(f,g) \\ \hat{L}_h(f,g) & = { 1\over n } \sum_{ (x,a,r, x') \in D_h } \left( f(x_{i, h}, a_{i, h}) - r(x_{i, h}, a_{i, h}) - g(x'_{i, h}) \right)^2 \\ \tilde{L}_h(f,g) & = { 1\over m } \sum_{ (x, a,r, x',) \in D'_{h}} \left( f(x, a) - r - g(x') \right)^2 \end{align}\]

where, as in the proof sketch, the \(\inf\) in the second line is also over all measurable functions. Finally, recall that, for any functions \(f, g \in (\mathcal{X}\times \mathcal{A}\to \mathbb{R})\), we have defined \[\begin{align} \| f -T^* g\|_{\mu_h}^2 := \mathbb{E}_{\mu_h} \left( f(x,a) - T^*g(x, a) \right)^2 \end{align}\] It is easy to see that this is equal to \(L_h(f,g)\) without the irreducible erorr: \(\| f - T^* g\|_{\mu_h}^2 = L_h(f, g) - L_h^*(g)\).

To proceed with the concentration analysis, we will show that all the necessary events will hold simultaneously with high probability. This requires defining some additional notation.

We let \(f^k = (f^k_h)_{h \in [H]} \leftarrow \mathcal{B}(D, \mathcal{F}_k)\) for each \(k \in [M]\). Then, for each \(h \in [H]\), we define the empirical minimizers for a larger class \(k'\) with the same regression target as follows: \[\begin{align} g^{k' \to k}_{h} = \mathop{\mathrm{arg\,min}}_{g \in \mathcal{F}_{k'}} \hat{L}_h(g, f^k_{h +1} ) \end{align}\] for all \(k' \geq k\). Not all of these need be computed in the execution of Algorithm 1, but we will analyze them all for the sake of simplicity in the concentration analysis. We define the following event that guarantees all of these value function approximators achieve their desired errors simultaneously up to log factors.

\[\begin{align} \mathcal{E}_1 = \bigcap_{k \in [M], k' > k, h \in [H]} \left\{ \| g^{k' \to k}_h - T^*_h f^k_{h +1 } \|_{\mu_h}^2 \leq 3 \mathrm{\small Approx}(\mathcal{F}_{k'}) + {C_1 H^2 \log( 8 M^2 H | \mathcal{F}_{k'} | /\delta) \over n } \right\} \end{align}\]

where \(C_1 > 0\) is a constant to be determined. The next event ensures that the base algorithm actually achieves its guarantees from Definition 2. \[\begin{align} \mathcal{E}_2 = \bigcap_{k \in [M], h \in [H]} \left\{ || f^k_h - T^*_h f^k_{h + 1} \|_{\mu}^2 \leq \beta \cdot \mathrm{\small Approx}(\mathcal{F}_{k}) + w_{n, \delta/ 4M}(\mathcal{F}_k) \right\} \end{align}\] The above \(\mathcal{E}_2\) occurs with probability at least \(1 - {\delta \over 4}\) essentially by definition of the base algorithm. The last event that we are interested in relates the true loss \(L_h\) to the validation loss \(\tilde{L}_h\) on the independent dataset \(D'\). We define \(\tilde{L}_h^*(f_{h + 1}^k) :=\tilde{L}_h(T^*_hf_{h + 1}^k, f_{h + 1}^k)\). The events are given by \[\begin{align} \mathcal{E}_3 & =\bigcap_{k \in [M], k' > k, h \in [H]} \left\{ \tilde{L}_h(g^{k' \to k}_h, f^k_{h + 1} ) - \tilde{L}^*_h(f^k_{h +1}) \leq 2 \left( L_h(g^{k' \to k}_h, f^k_{h + 1} ) - L^*_h(f^k_{h +1}) \right) + { C_3 H^2 \log(16HM^2 /\delta) \over m } \right\} \\ & \quad \bigcap \bigcap_{k \in [M], h \in [H]} \left\{ \tilde{L}_h(f^k_h, f^k_{h + 1} ) - \tilde{L}^*_h(f^k_{h +1}) \leq 2 \left( L_h(f^k_h, f^k_{h + 1} ) - L^*_h(f^k_{h +1}) \right) + { C_3 H^2 \log(16HM^2 /\delta) \over m } \right\} \\ \mathcal{E}_4 & = \bigcap_{k \in [M], k' > k, h \in [H]} \left\{ L_h(g^{k' \to k}_h, f^k_{h + 1} ) - L^*_h(f^k_{h +1}) \leq 2 \left( \tilde{L}_h(g^{k' \to k}_h, f^k_{h + 1} ) - \tilde{L}^*_h(f^k_{h +1}) \right) + {C_4 H^2 \log(16HM^2 /\delta) \over m } \right\} \\ & \quad \bigcap \bigcap_{k \in [M], h \in [H]} \left\{ L_h(f^k_h, f^k_{h + 1} ) - L^*_h(f^k_{h +1}) \leq 2 \left( \tilde{L}_h(f^k_h, f^k_{h + 1} ) - \tilde{L}^*_h(f^k_{h +1}) \right) + {C_4 H^2 \log(16HM^2 /\delta) \over m } \right\} \end{align}\] where \(C_3, C_4 > 0\) are constants to be determined. We will prove the following guarantee.

To prove this result, we will show that these events occur with high probability. We require several intermediate results, starting simply with Bernstein’s inequality.

The next lemma is a generalization error bound showing that the Bellman error of a function \(f \in \mathcal{F}\) can be bounded in terms of the excess training loss, the approximation error of \(\mathcal{F}\), and the estimation error which is \(\tilde{\mathcal{O}}(\log|\mathcal{F}| / n )\). The next lemma shows that the minimizer of the empirical squared loss achieves good generalization error with respect to the optimal function in its class.

Note that if we take \(f = \hat{f}_h\) to be the empirical minimizer of \(\hat{L}_h(\cdot, g)\), then the bound in Lemma 3 becomes \[\begin{align} \| \hat{f}_h - T^*_h g \|_{\mu_h}^2 & \leq 3 \| f^* - T^*_h g \|_{\mu_h}^2 + {40 (H + 1)^2 \log (2 | \mathcal{F} |/\delta) \over n} \\ & \leq 3 \mathrm{\small Approx}(\mathcal{F}) + {40 (H + 1)^2 \log (2 | \mathcal{F} |/\delta) \over n} \end{align}\] where the last inequality follows because \(\mathcal{G}\subseteq\mathcal{F}\). Equipped with these bounds, we are now ready to prove that event \(\mathcal{E}_1\) holds with good probability.

8.3 Proof of Theorem [thm::main]↩︎

Armed with the concentration results of the previous section, we are ready to prove Theorem [thm::main], which is restated here for clarity.

8.4 Proof of Theorem [thm::robust]↩︎

9 FQI Algorithm and Guarantees↩︎

Here we state and then prove a more detailed version of the FQI guarantee that was originally stated in Lemma [lem::fqi].

We may now apply this result to immediately Corollaries [cor::fqi] and [cor::fqi-robust].

10 Experiment Details↩︎

10.1 Practical Implementation of ModBE for the RL Setting↩︎

ModBE, as stated in Algorithm 1, is originally designed for the finite horizon case in which there are \(H\) functions comprising the value function approximators. For the contextual bandit setting (where \(H = 1\)), we make no modifications. In an effort to further increase the computational and statistical efficiency of ModBE in the RL setting (as well as to demonstrate that its primary principles are fairly robust), we opted for a discounted infinite horizon implementation with discount factor \(\gamma = 0.99\) (default for d3rlpy).

We use a single fixed dataset \(D\) (not split into timesteps) and fed this to the Deep Q-Network (DQN) implementation of [51] using all the default hyperparameters except for the network architecture, which was specific to each model class as described in Section 5. For consistency, we set the number of epochs to 20 across all model classes and experiments for DQN. This generates value function approximators \(f^1, \ldots, f^M\). To implement a close approximation of Algorithm 1 in discounted case, considered the following procedure. While the algorithm is on model class \(k\), we compute empirical risk minimizers for \(k' \geq k\) so that \[\begin{align} g^{k'} \leftarrow \mathop{\mathrm{arg\,min}}_{g \in \mathcal{F}_{k'}} \; {1 \over n_{\text{train}}} \sum_{(x, a, r, x') \in D_{\text{train}} } ( g(x, a) - r - \gamma f^k(x'))^2 \end{align}\] We then decide whether to switch to \(k + 1\) by using the generalization test: \[\begin{align} \tilde{L}(g^{k'}, f^k) \geq \tilde{L}(g^{k}, f^k) - \mathrm{\small Tol}_{n_{\text{train}}} ( \mathcal{F}_k, \mathcal{F}_{k'}) \end{align}\] where the functional \(\tilde{L}(\cdot, f^k)\) is the estimated loss on the validation data, as before: \[\begin{align} \tilde{L}(g, f^k) = {1 \over n_{\text{valid}}} \sum_{(x, a, r, x') \in D_{\text{valid}} } ( g(x, a) - r - \gamma f^k(x'))^2 \end{align}\] As noted in Section 5, we did not find it necessary to tune the any parameters related to \(\mathrm{\small Tol}_{n_{\text{train}}}(\mathcal{F}_{k}, \mathcal{F}_{k'})\) and simply set it to \({d_{k'} \over n}\) where \(d_k\) is the dimension of the linar model (for the contextual bandit setting) or the number of hidden nodes in the neural network (for the RL settings), which roughly (up to constants and logarithmic factors) matches known bounds on the pseudo-dimension [53]. The lack of necessity to actually make \(\mathrm{\small Tol}\) theoretically valid is actually a positive of the algorithm: it shows it is fairly robust in practice and simply matching the order appears to be good enough to generate the current results. To fit the empirical risk minimizers in the CB setting, we simply used ridge regression as in [28]. To do the same in the RL setting, we trained neural networks of with the same architectures as the DQNs in d3rlpy (state inputs and one output per action to predict the value). We used an Adam optimizer with on 10 epochs with a learning rate of 4e-3 and a batch size of 64. This was implemented through PyTorch [55].

One might ask whether it is possible to extend this beyond neural networks with one hidden layer. In practice one can easily use any model, but, in theory, some care may need to be taken in order to set the value of \(\mathrm{\small Tol}_{n_{\text{train}}}\). For example, to handle more hidden layers, we can appeal to generalized pseudo-dimension bounds [53]. As observed in the current experiments, the setting of \(\mathrm{\small Tol}_{n_{\text{train}}}\) to rough estimates does not seem to make a huge impact on the results.

10.1.0.1 Hold-out baseline

The hold-out method as a model selection baseline was implemented by choosing \(k\) that minimizes \(\tilde{L}(f^k, f^k)\) in the RL setting. In the contextual bandit setting it is equivalent to selecting \(k\) to minimize \(\tilde{L}(f^k, 0)\), since there is only one step.

10.2 Experimental Setups↩︎

We now describe the specific experimental setup so that it may be reproduced. In order to generate the plots which vary based on the sample size of \(D\), we simply curtailed the dataset to the given amount of samples shown on the \(x\)-axis. Generation of the datasets varied in each domain. It would be interesting in the future to evaluate performance on more stochastic RL environments (the CB evnironment is stochastic) as these are ones we expect toe Hold-out method to do very poorly on. Despite this, our current experiments show it is already sub-optimal even in deterministic settings.

10.2.0.1 Contextual Bandit

We replicated almost exactly the study of [28]. To recap their study, there is a linear contextual bandit with \(|\mathcal{A}| = 10\) and an infinite state space where the linear feature vectors of ambient dimension \(d = 200\) for each action are generated by sampling from normal distributions with different covariance matrices. The reward function is generated by taking the inner product of \(\theta_*\) with feature vector for action \(a \in \mathcal{A}\). To make this an interesting model selection problem, only the first \(d_* = 30\) coordinates are non-zero (although this is not known to the learner) and thus a model class using only the first \(d_*\) coordinates is sufficient to solve the problem without any approximation error. The individual model classes were generated by simply truncating the coordinates of the feature vectors to the following sizes \(\{ 15, 20, 25, 28, 29, 30, 50, 75, 100, 200\}\). The base algorithm was Algorithm 1 of [28].

One difference is that we included several additional model classes to the \(d_* = 30\) model that are close enough to fool the SLOPE algorithm used in [28]. This also involved increasing the ambient dimension from \(d = 100\) to \(d = 200\), but we kept \(d_* = 30\). We suspect that this poor performance of SLOPE is due to the fact that SLOPE is heavily dependent on the known deviation bounds whereas ModBE seems to be comparatively robust. The results of SLOPE seem to be poor whenever the deviation bounds are invalid or too conservative.

10.2.0.2 CartPole

We used the default dataset from d3rlpy [51] which contains approximately 1500 episodes of a good (but not optimal) behavior policy on the CartPole domain. Everything else remains the same as the standard CartPole environment in Gym [50].

10.2.0.3 MountainCar

Since no default dataset for MountainCar is provided in d3rlpy, we generated our own through the following procedure. First, we trained a policy online via SARSA on the discretized environment to achieve good performance on the task. We then collected the offline policy by executing 1000 episodes under the good policy which also took a random action at any time step with probability \(0.3\) to induce some coverage on the dataset. To simplify the problem for the base DQN algorithm, we also replaced the sparse reward in the offline dataset with a more dense and informative reward function, giving bonuses for high speeds, proximity to the goal, and achieving the goal. We note that this change is done only to simplify the problem and help the base algorithm solve the task with limited computational resources and tuning so as to increase reproducibility. Everything else remains the same as the standard MountainCar environment in Gym [50].

10.3 Hardware↩︎

Contextual bandit experiments were run on a standard personal laptop with 16 GB of memory and an Intel Core i7 processor. RL experiments were run on an internal cluster with 16 GB of memory and an NVIDIA GTX 1080 Ti GPU for PyTorch [55].

References↩︎