Oracle Inequalities for Model Selection in Offline Reinforcement Learning
Authors: Jonathan Lee
George Tucker
Ofir Nachum
Bo Dai
Emma Brunskill
Venue: NeurIPS 2022 Accept (2022)
Keywords: offline reinforcement learning
reinforcement learning
model selection

Abstract: In offline reinforcement learning (RL), a learner leverages prior logged data to learn a good policy without interacting with the environment. A major challenge in applying such methods in practice is the lack of both theoretically principled and practical tools for model selection and evaluation. To address this, we study the problem of model selection in offline RL with value function approximation. The learner is given a nested sequence of model classes to minimize squared Bellman error and must select among these to achieve a balance between approximation and estimation error of the classes. We propose the first model selection algorithm for offline RL that achieves minimax rate-optimal oracle inequalities up to logarithmic factors. The algorithm, ModBE, takes as input a collection of candidate model classes and a generic base offline RL algorithm. By successively eliminating model classes using a novel one-sided generalization test, ModBE returns a policy with regret scaling with the complexity of the minimally complete model class. In addition to its theoretical guarantees, it is conceptually simple and computationally efficient, amounting to solving a series of square loss regression problems and then comparing relative square loss between classes. We conclude with several numerical simulations showing it is capable of reliably selecting a good model class.

Oracle Inequalities for Model Selection in Offline Reinforcement Learning
Jonathan N. Lee
George Tucker Google Research gj t0google com
Stanford University jn jnl@stanfo ord. edu
Ofir Nachum Google Research of iirnachu@@googge.comm com
Bo Dai Google Research
Emma Brunskill Stanford University ebrunêcs stanford edu
bodai Modai@google..o com
Abstract
offline reinforcement learning (RL), a learner leverages prior logged data to learn a good policy without interacting with the environment. A major challenge in applying such methods in practice is the lack of both theoretically principled and practical tools for model selection and evaluation. To address this, study the problem of model selection in offline RL with value function approximation. The learner is given nested sequence of model classes to minimize squared Bellman error and must select among these to achieve a balance between approximation and estimation error of the classes. We propose the first model selection algorithm for offline RL that achieves minimax rate- optimal oracle inqqualities up to logarithmic factors. The algorithm, MODBE, takes input collection of candidate model classes and a generic base offline RI. algorithm. By successively eliminating model classes using novel one-sided generalization test, MODBE returns policy with regret scaling with the complexity of the minimally complete model class. addition its theoretical guarantees, is conceptually simple and computationally efficient, amounting to solving series of square loss regression problems and then comparing relative square loss between classes. We conclude with several numerical simulations showing it is capable of reliably selecting good model class.
Introduction
Model selection is a fundamental task in supervised learning and statistical learning theory. Given a sequence of model classes, the goal 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 learning theory (Massart, 2007; Lugosi and Nobel, 1999; Bartlett et al., 2002; Bartlett, 2008), and methods like cross cross-validend validation have become essential steps for practitioners.
In recent years, interest has turned to model selection in decision- decision-making problems like bandits and rein- forcement learning. number of theoretical works have studied the online setting (Agarwal al., 2017; Foster et al., 2019; Pacchiano et al., 2020; Lee et al., 2021 a; Modi et al., 2020; Chatterji et al., 2020; Muthukumar and Krishnamurthy, 2021). Similar to the bias-variance balance in supervised learning, these algorithms typically aim select the model class with smallest statistical complexity that contains true model. Despite these recent efforts, the current understanding model selection in offline (or batch) reinforcement learning (RL) is comparatively nascent. Offline RL is paradigm where the
SSuppeementary material is available
model-selection.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

learner leverages prior datasets of logged interactions with the environment (Lange et al., 2012; Levine et al., 2020). The learner is tasked with returning a good policy without further environment interaction. As has been acknowledged in several recent papers (Xie and Jiang, 2021; Mandlekar et al., 2021; Kumar et al., 2021), one of the major challenges preventing widespread deployment of offline RI. algorithss 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 (Kumar et al., 2021; Tang and Wiens, 2021; Paine et al., 2020). 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 shelf offline policy evaluation (OPE) methods (Precup, 2000; Thomas and Brunskill, 2016). 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 (Foster et al., 2019; Pacchiano et al., 2020; Lee et al., 2021a). 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 (Foster et al., 2021; Zanette, 2021; Wang et al., 2020). Perhaps the most widely used and recognized condition is completeness (Munos and Szepesvári, 2008; Antos et al., 2008; Chen and Jiang, 2019) which essentially says that T & for any fEF, where T is the Bellman operator and F is the model class. 3 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 Xie and Jiang (202 I); Zhang and Jiang (2021)). 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 RL. Lee et al. (2021b) lb) 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 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
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 single model class using value-based methods. For any individual model class F that satisfies completeness and an offline dataset of n samples with sufficient coverage, the gold-standard regret
bound is Ö (v COMP(FF/n)) where COMP(F) denotes the statistical complexity of F. This is achieved, for example, by Fitted Q-Iteration (FQI) (Chen and Jiang, 2019). Clearly, one would like COMP(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 nested sequence of M model classes Fi C ... FMr We investigate the following question: Can
That is. conditions sufficient for supervised learning, like realizability, tend not to be sufficient on their own for offline RI.
3f is a model class meant to estimate Q-functions. It consists of functions mapping state-action pairs to value predictions. The Bellman operator applied to f E F pointwise is defined as T fz a) r(z,a) + 1er .a))-
'orr clarity, Ô omits dependence on certain parameters such as the horizon H. distribution mismatch factors, number of classes M, failure probability 6, log factors, and constants.

---

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. Theorem 1. (informal version of Corollary 1) Given an offline dataset of samples and nested model classes Fi C C..... FMM MODBE oulputs it such that Reg(#)= = Ô ( (CoMP((s..//) where k. m E [M] F& is complete):
A guarantee of this nature is typically known as 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 COMP(FE, ) and n, showing that do not have sacrifice efficiency for adaptivity. This is in contrast to some other works in model selection for decision-making where this unfortunate -adiieeccaaaapiiviityy trade-off has been observed (Foster al., 2019; Pacchiano et al., 2020; Xie and Jiang, 2021). In Appendix A, we discuss how the nestedness condition is necessary.
We also provide robustness result for model selection (Theorem 3): if no models are Bellman complete (that is, k, does not exist), MODBE obtains Reg At S Ô miinse[ar + COMP where Ê
is a measure of the global completeness error of F 5 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.
Technical Highlights. The key to achieving the near optimal regret rate to achieve the near optimal excess risk rate of the squared Bellman error (which is of order Ô (COMP(FF../m))
To do this, MODBE iteratively compares the relative effectiveness of two candidate model classes by employing hypothesis test that compares the difference 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 Ö( (/m which translates to slow Ó ((COMM(FFR)) //)F////))//////)//// regret rate. Instead the one-
sided generalization error allows us to ultimately obtain the optimal Ö (C.MP(FFs./// regret rate.
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 O (HHk, calls to an empirical squared loss minimization oracle and 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 theoretical perspective, as we do here. Lee et al. (2021b) formalized the and-to-end model selection problem for offline RL where, given nested model classes, the goal is to produce 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 Farahmand and Szepesvári (201 1) had partially addressed our problem but made several restrictive assumptions such 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 Xie and Jiang (2021). While initially designed for general policy optimization, BVF can be applied to model selection (Zhang and Jiang, 2021) but it incurs a slow 1 1/n regret rate in theory (compared to our 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. Jiang et al. (2015) studied abstraction selection between nested state abstractions of increasing granularity; however,
Seee Section 3.1 for precise definition.
3

---

this eschews problems specific to value function approximation setting. Hallak et al. (2013) 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
Notation For any N. we let [n] n.). The notation a a b implies that S Cb for some absolute constant C > O. We will use C,C1,C2...> > O to denote absolute constants (independent of problem parameters). For set A, (AA) denotes the set of distributions over A.
We consider the finite-horizon Markov decision process M,.',,,,, infinite) state-space, A is the action space, H is the length of the horizon, P: X x A + A(X) is the transition kernel A [0.1] is a deterministic reward function, and p A (xt) is an initial state distribution. A learner interacts with the MDP by proposing H step policy
where X' is the (potentially
(IT) he(r) where
each TA = (+|x) maps x E X' a distribution over actions in (AA) 6 At step h = 1, ii drawn according to p. Then at step E [H] the agent observes Th. draws on according to Ta (-(ax) observes reward ( (4)) and the MDP transitions to T4+1 according to P( For policy m, let PT (z,a) and P (z) denote the marginal state-action and state densities of T respectively at step h.
Following standard definitions, we let VØ X' + R denote the value function of π at step h E [H] which is given by V (x) = Ex (x2a)( I, = Here, the expectation E,, is over trajectories under π with ag ~ The (1 Similarly, the action-value function Q7, X' x A - R is defined as (= 22 I. =,,0, =a The optimal policy (which exists under conditions when H is finite (Sutton and Barto, 2018)) is denoted by π and this maximizes Vž (x) for all x define
and h. The average value of policy is given by U(T) := Ex-p [VT(x)). Finally,
the Bellman operators: TH (1x ((r,))=((a r(x,a) + Pe a (112)) (Q(''aaa)) and Th (1r,a) = r r(x,a)++EE + MaaxxaeAQQi ,a ]. Note that the values of (TT), V and Q7, are always in [0,H] due to the constraint
convenieeee,, we denote the Q function of the optimal policy as Q = Q"
We consider the setting where the learner is provided with a model class J C (X' - [0. HJ) to estimate action value functions at each step. For exposition, we assume this model class is finite; however, is straightforward extend to infinite settings with appropriate complexity measures. For simplicity, we will assume that the learner uses the same F for each timestep / E [H] but this is trivially extended. We assume that 0 F and we always write fH+1 = O. For any function f E X' x [O.H). we define the argmax policy Ty (I) = argmax, af (x,.a. We will also write f(x) max. Af (I,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 dataset D of example transitions in the MDP. The learner itself is not permitted interact in the environment. The objective is to produce good policy á using only data from the dataset D.
Formally, the dataset decomposes as D = ( for each timestep where D₁ ((,,a.r,z") consists of tuples of transitions and incurred rewards. We assume D2, contains n datapoints that are sampled i.i.d from fixed marginal distribution f4a E A x A) and the data are independent across timesteps h. That is, there are H n. datapoints total. For example, the data could be generated from lo-step state-action distribution of a behavior policy " so that pm (x, = P (xxa)= (aa)=)n (a (P (z).
For f.g E (X' x A RR, we use the notation - = Eys ((((.))))(z=0))] The average squared Bellman error under μ at state h with respect to f.g is f -T: Following classical conventions (Munos and Szepesvári, 2008; Duan al., 2021), we make concentrability assumption that the data distribution y has good coverage over the MDP for all reachable state-actions.
Assumption 1. There exists a constant C(p) > 0 such that su,,, PA (r,4)/ (2,a) SC()).
Concentrability is a structural assumption and it is widely regarded as perhaps the most standard assumption when studying offline RL problems (Foster al., 2021). We remark that recent theoretical
With some abuse of notation, for deterministic na write === (x: to denote its probabbi-y action.

---

works have striven to weaken this condition via pessimistic methods (Liu et al., 2020; Jin et al., 2021; Xie et al., 2021: Uchara and Sun, 2021). However, Theorem 2 of Lee al. (2021b) 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.
result, we will not consider this refinement in the present paper.
In this offline setting, the learner aims to use D and F to produce policy स so as to minimize the regret, which measures the difference in average value between the optimal policy IT" and #:
Reg (t) :
(1)
The following variant of the performance difference lemma will be used throughout the paper (Duan et al., 2021). It shows that it is sufficient to control the squared Bellman error to bound regret.
Lemma 1. For SH, let æ:
Then, 52 (( - -T7, S1
3 Model Selection Objectives
In this section, state our primary model selection objectives and discuss their significance well as challenges associated with solving them.
3.1 The Model Selection Problem
For finite function class F that we consider here, the gold-standard regret guarantee for offline algorithms with value function approximation
Reg(f)) = (VVC))(OVOOXOX
C(H) F n
where : (Chen and Jiang, 2019). This is achieved, for example, by the Fitted Q-Iteration (FQI) algorithm. If we were using infinite classes, we would replace log FF with suitable notion of complexity such as pseudodimension. Such bounds naturally exhibit a trade-off: larger classes may have better chance of keeping APPROx(FF (F) close zero? but require more data to minimize the estimation error. Small classes face the opposite problem.
1' [|
is the completeness error of the class F
Definition 1. A class F is complete if APPROx /
The objective of model selection is to achieve refined regret bounds that balance approximation and estimation error. To this end, we assume that the learner is presented with not just a single model class F. but rather nested sequence of M classes Fi C... Far. Nested model classes supervised learning and offline RL. For example, one often starts with an extremely large class F and then considers restrictions of F an increasing sequence Fi C... F =F. a linear setting, this could correspond to trying to find subset of candidate features that are sufficient to solve the problem.
common in both
Since the approximation error is typically unknown priori, aim to design algorithm capable of selecting a good class in a data-depender manner. In particular, we would like to achieve oracle inequal- ities reflecting that can compete with the performance of oracle that has this knowledge in advance.
Our primary objective is to compete with the minimally complete model class.
Problem 1. Let k. = min k [M] F& is complete). Find स with Reg (ft -
Here, Fx. is the smallest class that satisfies completeness on the data distribution. Such oracle inequalities are common in model selection for online bandits and RL (Foster et al., 2019) albeit they are generally not rate-optimal in that literature. In particular, Problem 1 states the regret bound should achieve the same dependence on Fo. and n, as would an optimal offline algorithm using single class with k k.. In other words, we do not tolerate any worse dependence on either quantity such O (1/m2/44 rates and other lower order terms.
We are also interested in a robustness when k. may not exist, i.e. all Fy have some approximation error.
In contrast to realizability,, this intuition of monotonicity of AFPROx(F) is not universally true for complete- ness. Adding functions to the class F might actually increase APPROx(F), However, it remains a useful heuristic. In Appendix A. discuss how model selection in this setting is not possible without nestedness.
5

---

Problem 2. Define the global completeness enror as ma min minjer, Find it so that Reg( Rt ① minneear { (CCW))=++((())00(((())
Note that & APPROx 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 solution to the other. For example, a class Fi may be complete, but & 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 number of seemingly natural approaches model selection in RL that are surprisingly unable to produce satisfactory results, at least off-the-shelf.
Adaptive offline policy evaluation The most natural approach, to which we have alluded in the introduction, is to first compute 7& with base algorithm using function class Fk. for each & E [M]. Then, one can estimate v(fx)) using an off-the-shelf offline policy evaluation approach such as fitted Q-evaluation (Munos and Szepesvári, 2008; Duan et al., 2020), DICE methods (Nachum et al., 2019; Dai et al., 2020; Zhan et al., 2022), marginalized importance estimators (Xie et al., 2019), or doubly robust estimators (Jiang and Li, 2016; Thomas and Brunskill, 2016). Then one simply picks the fx 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 Su et al. (2020), 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 Lee al. (2021b) 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 C(u). Since these bounds are required by the adaptive estimator as inputs, we are yet again left with unknown hyperparameters to tune.
Bellman error estimators Recall we are focusing on base offline RL algorithms that attempt to mini- mize 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 proxy. Consider, for example, FQI which iteratively minimizes the squared Bellman error:
fn = =argminEp, ((((r,))--mgxxfnr (2)) JEF
where we use ED, denote the empirical mean calculated with samples from the dataset D Presumably, we could simply choose the model class Fs that has the smallest cumulative squared error. The main issue with this approach is the classic double-sampling problem (Baird, 1995; Duan et al., 2021): ): the standard estimator of the Bellman error is biased because of the empirical version of the Bellman operator T** With this selection criterion, we will end up favoring model classes that also induce low variance of the regression targets, given by r fn+z (x')
at step h because the expectation is
Exp.. (file,a)-r-
27 =1l -(AC
Jr+1 pm. + +E
var (P-P(()),)) (fins(ee))
We want to choose a class F& to minimize only the first term on the right-hand side, summed over h E [H], following Lemma 1. However, the second term is generally unknown. One could assume there a sufficiently powerful class G such that T ff & for all f (Chang et al., 2022). But there remains question of how to select the class 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 the BVFT algorithm of Xie and Jiang (2021) to select among the f learned by the base algorithm. This solves the model selection problem but B BVF has slow (11/n dependence. It also, in theory, requires that a discretization parameter is set based on a concentrability coefficient stronger than C(1).
For marginalized importance sampling, the guarantee is not strong enough compete with the oracle.

---

which is typically unknown. Perhaps most conceptually related is past work which compares Bellman errors of finer- sner-grained state abstraction functions on the Q-function computed on coarser- -rain state abstraction (Jiang et al., 2015). This work provided regret bounds on in the discrete state and action setting where the models are varying levels of state abstractions. However, this critically depends on the discrete state and action setting. Our work shows how similar idea can be used in the value function approximation setting, with substantially different tools and analysis techniques.
Representation Learning Model selection resembles objectives in representation learning for RL (Agarwal et al., 2020; Modi et al., 2021). However, we cannot simply adapt such algorithms since they are either insensitive to the class complexities or they require stronger realizability assumptions. Understanding the connections of these problems would be interesting for future work.
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 aforemennioned oracle inequalities. We first give an intuitive sketch of the approach. As a thought experiment, we will consider the case when M = 2 and minimally complete class Fk. exists." 2 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 base algorithm like FQI with Fi on training data returns the functions fi,...,HH which, with high probability, satisfy Ex - 1 Ō
((())log([Fil) (
if k. 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:
(x.arrr)) (g(x,a)-r-- (rotaa----ffa220 f
Let (f.g) =- := Emn Ln (f-9)) Solving this regression problem for each h over the class F2 will generate 91H F2. The key insight is that the sequences (fr) and (g))), are both trying to minimize the same empirical square loss function with the same regression targets: r + fh+11 (z'). Unlike the Bellman error estimators from the previous section that incur biases, the losses L2 (fn.ff+1) and Li(gh, fa+1)) ) are comparable and estimable from a validation set. By nestedness of Fi S F2 cannot have more approximation error on this regression problem. Provided we can get a good estimate of generalization errors (n 1) and (9(.ff with validation data, this naturally brings forth the following generalization test: if
L (9hhShtt ) In In(JnsSh+1))
(og(LAD n
reject Fi and pick F2.. Otherwise pick Fi. That is, switch will occur not when F2 performs only marginally better than F1. but when it performs substantially better as measured by the generalization error that we see for both fn. and 9n on this regression problem. (3) holds, then there is reason to believe that Fi is not complete, making F2 the right choice. Crucially, the test only checks for generalization error, so the tolerance term on the right side goes as Ö(log( /n)) 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 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 Fi C...C.FF C.M- and the offline dataset D E [.... The dataset is split randomly into a training set Duain and a validation set D The algorithm begins optimistically, starting with the candidate model class & = I and running the base algorithm with F& on the training dataset to generate the candidate functions f. We
Whiile the full algorithm requires minimal changes beyond this intuition there are challenges in the proof. For general M, we cannot guarantee the class returned will be the correct but it may have controllable approximation error. When k. does not exist, there is chance to "skip" the best model class.
7

---

Algorithm 1 Model Selection via Bellman Error (MoDBE)
1: Input: Offline dataset D = ) of samples for each h E [H]. Base algorithm B, function classes Fi I.... ... F.M failure probability 8 1/e, and estimation error function for B.
2: Let Alrrain = [0.8-n] and Avalid [0.2 and split the dataset D randomly into Duain (Draii,
of Murii samples and D Dalidd ( ) of Aiaaid samples for each h E (H).
3: Setç:= 96H logGM H/5)
Praia
4: Initialize k
5: while 1: M do
6: (Jn)NE(H) <- F
7: for k' do
8: Seta:=max 6/ 6/1M (F
300tH"lo((8."" M FFF1.18))
9: Set ToL:=2a> Wean 8/4M (F&)
Minimize squared loss on training set for h E [H) with regression targets from class k:
Ih 4 argmin Ln(g.fh+))==
Σ
(0(2,a)-r- fn)))
(4)
gEFF
Terain (rr,a,r,a")e Dann
Compute squared loss using the validation for all h [H] as function f:
in(fff(tz)=
E
(f(zn,a)) - f
(5)
Tivalid
(x,e.r,"")Deaae.
(gn,sfhh Ln (fh ToI. for any he [H] then
13:
kt k+1
goto Line end if
15:
end for
17:
goto Line 19 end while
19:
return A (TT
retrain the empirical square loss using class k' l by regressing target values + fu+ (z'). This amounts to solving a sequence H least squares regression problems using class ky, yielding the functions 9h- Since fa and gI attempting to solve the same regression problem (with the same target values), validation data. We use a generalization error test in Line 12 to decide whether to keep using class k. the test fails and is discovered that the larger model class Fig is able to achieve substantially smaller loss than FA. then we move to a larger model class 1 t k 1. The process is repeated until all classes exhausted or model class k' offers big enough improvement over cause the test to fail.
compare their performance on this shared squared loss objective L with
4.2 Rate-Optimal Oracle Inequalities
We show that MODBE is able to achieve both Problems I and 2 simultaneously. We start with generic version of the theorem stated terms of an assumed performance bound w on the base algorithm. We will presently instantiate the base algorithm with FQI, showing that it precisely achieves the oracle inequalities with the correct rates.
Definition 2. Let B be a hase offline RL. algorithm for value function approximation that takes as input a model class F, an offline dataset D of samples for each h E [H), and a failure probability 5. For 3 0 and function we say that B is - (1) w is known real-values functiooooiooooo of E N, R, and Fs, and satisfies wn. FFx) S S.n (FF) for all 2 (2) ((D, returns (Jn) he(a C FR such that J1+1 is independent of Dr. and
P
max KE(H
fh TT, 11 < (F.
2-
Here, 39 scales the approximation error and represents the estimation error. Generally, we will have Wn.s = ((00((()))() (see Lemma for FQI). We hope to achieve a bound that matches what the base algorithm would achieve had k, been known in advance, up to additive terms of //lo((FF.. 1)/n.

---

Our primary theorem addresses Problem using an arbitrary base algorithm.
Theorem 2. Let B be an (B,w)-regular algorithm and suppose that k. (defined in Problem 1) exists. Let Lo [ / Then. for some absolute constant C 0, Algorithm I with inputs D, B, F.....CFF w, and 5 $ 1/e outputs ît such that, with probability at least 1-8,
H (2
++))
Reg Reg(A) C W Menato 5/4M (Fk.)
The above theorem shows regret bound scaling with the square root the error term w of the base algorithm B plus (log(([F,, I)/n) estimation error. Importantly, as stated in Problem 1. the statistical complexity depends only on Fx. and not any of the larger classes. For concreteness, we now instantiate Theorem 2 with standard
FQI (Duan et al., 2020) base algorithm, which satisfies Defini- tion with win, (F)= (log).FF /n). This in turn translates to the desired rate-optimal oracle inequalities. Lemma 2. Consider the FQI algorithm (stated Appendix for completeness), For a model class F. FQI is a (3,w)- base algorithm with 5 (F)) = 11 H (1/88)
By plugging this classic result in Theorem as the base algorithm, we arrive at a solution to Problem 1. Corollary 1.
Let B be instantiated with FQI (Algorithm 3 in Appendix C). Define t= t= (og H/6). Then, under the same conditions as Theorem 2, there is an absolute constant C > O Ouchh that, with probability least 1 6- Algorithm 1 outputs satisfying
Reg(#) SC.V C(u) FL, H+)
The proof Theoremm 2 (Corollary 1) follows the intuition from the start this section. The proof shows (1) MODBE will never return value of k that exceeds k. and (2) if MODBE returns k < k,, then the approximation error must be small. key novelty recognizing that the generalization test Line 12, which compares the errors classes on the same regression problem, can be used to prove both (1) and (2).
Robustness We show that the same Algorithm simultaneously achieves the desired robustness result of Problem 2 when k. does not exist without any modification.
Theorem 3. Under the same conditions as Theorem if ki does not exist, there exists an absolute constant C> 0 such that, with probability at least - ô, Algorithm I outputs it satisfying
CLNDE B.Ex (.EA- W Wr 8/4M (Fa)+ H2([lg] +1) }
}
Reg(f) Reg(+))CC
SC- min kE[M]
(9)
We can Lemma to solution to Problem with instantiation of FQI. Corollary 2. Under the same conditions as Corollary 1, there is an absolute constant C' > 0 such that, with probability at least 1-ô, ô, Algorithm I outputs ā satisfying
Reg(#) (t < C-minee (C(N))ER +
C(H) +c)
(10)
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. The proof of Theorem 3 (Corollary Here, we allow & to exceed the minimal index sometimes. We then use the fact that class (A (6-1] 1) must have failed the generalization test to argue that the estimation error of the larger class can be bounded by the unknown - which is small since k exceeds the index of the minimal class.
more involved, but still crucially leverages the generalization test Line 12.
Computational Complexity MODBE computationally efficient given 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 O(Hk,M) calls to the computational oracle when k. exists (a consequence of Theorem 2) or (HH22 the worst case. Note that algorithms for optimizing squared loss regression problems ubiquitous in machine learning (Simchi-Lew and Xu, 2021).

---

Coneectul BandR
CartPole
NountainCar
1.
Hodd--d
23390
N2237
-20
25
140
1996
100
tepisoces)
Figure 1: MODBE evalusted several simulated domains: contextual bandit (left), CartPole (middle). Mountannar ar (right). CB, MODBE and Hold-out ourperform SLOPE and match performance of the best model class in regret. In CartPole, both match the performance of the best model class. In MountainCar, Car, both struggle to match best model class, but MODBE BE maintains superior performance. In CB, error bands standard error 10 random trials. In RL., error bands standard error 20 random trials.
5 Empirical Results
The previous sections outlined the strong theoretical properties of MODBE. In this section, we ask: what practical insights 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: (I) synthetic contextual bandits (CB), (2) Gym CartPole, (3) Gym MountainCar See Appendix D for specific details about the setups. All training and validation sets were split 80/20.
Contextual Bandit As a basic validation experiment, we started with the CB setting of Lee et al. (2021b) which considers a nested sequence of linear model classes with increasing dimension d. Without any tuning, we simply set the tolerance of MODBE to ToL(FF,FFe) = duf Figure 1 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 (Lee et al., bb2 ends up being fooled by nearby classes.
n
RL Discrete Control Our setup for the RL problems in Gym (Brockman et al., 2016) builds on top of the open-source d3ripy framework (Seno and Imai, 2021). We used DQN (Mnih et al., 2015), which is closest to FQI. 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 dy/ n motivated by pseudodimension bounds (Bartlett al., 2019). For simplicity, we modified MODBE to work in the discounted infinite horizon setting, which can trivially be done (see Appendix D). We compared MODBE to Hold-Out, which is a seemingly sensible baseline that chooses the model class with lowest estimated Bellman error on validation set. For deterministic settings only, this is theoretically justified. Figure shows the reward as a function of the dataset size (in episodes). On CartPole, MODBE marginally outperforms Hold-Out. 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 is possibly due to sensitivity to optimization error making the Bellman error misleading. In contrast, the generalization test of MODBE. E. seems to be more robust.
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- rate-optimal oracle inequalities in and COMP (F..) ). A number of interesting open questions remain. (I) Are there rate-optimal procedures that can be used to select hy- perparameters beyond model complexity such 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 is potentially much worse than APPROX Is it possible achieve a robust oracle inequality of the form O O(ming / (F.) F///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.
Acknowledgments and Disclosure of Funding
We thank Annie Xie and Yannis Flet-Berliae for help and advice with experiments and anonymous reviewers for their valuable feedback. JNL. supported by the NSF GRFP, This work was also supported in part by NSF Grant #21 12926.
10

---

References
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert Schapire. Corralling a band of bandit algorithms. In Conference Learning l'heory, pages 12-38. PMLR, 2017.
Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-200 2010,,,,-017,00000000 2020.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89-129, 2008.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier, 1995.
Peter Bartlett. Fast rates for estimation error and oracle inequalities for model selection, Econometric Theooy, pages 545-552, 2008.
Peter L Bartlett, Stéphane Boucheron, and Gábor Lugosi. Model selection and error estimation. Machine Learning, 48( 48(1):85--13, 2002.
Peter I. Bartlett, Nick Harvey, Christopher I Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2300 2019.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym (2016). arXiv preprint
2016.
Jonathan Chang, Kaiwen Wang, Nathan Kallus, and Wen Sun. Learning bellman complete representations for offline policy evaluation. In International Conference Machine Learning. pages 2938-29277 2971. PMLR, 2022.
Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett. Osom: A simultancously optimal algorithm for multi--rmee and linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages I 1844-1854, 2020.
Jinglin Chen and Nan Jiang. Entormation-thoorete considerations in batch reinforcement learning. In International Conference Machine Learming, pages 1042-1051. PMLR, 2019.
Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. Advances in neural information processing systems, 33:9398 9,11, 2020.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax -otimmal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709, PMLR, 2020.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference on Machine Learning, pages 2892-2902. PMLR, 2021.
Amir-massoud Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Machine learning, 85(3):299-332. 201
Dylan Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. arXiv preprint arXiv:1906.000331/
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10911, 2021.
Assaf Hallak, Dotan Di-Castro, and Shie Mannor. Model selection in markovian processes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 374-382, 2013, 2013.

---

Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning, In International Conference on Machine Learning. pages 652-661. PMLR, 2016.
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model- reinforcement learning. In International Conference on Machine Learning, pages 179-188. PMLR, 2015.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5096. PMLR, 2021.
Aviral Kumar, Anikait Singh, Stephen Tian, Chelsea Finn, and Sergey Levine. A workflow for offline model-free robotic reinforcement learning. arXiv preprint S.ii::209.108133, 2021.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3340-3344 3340-3348. PMLR, 2021a.
Jonathan Lee, George Tucker, Ofir Nachum, and Bo Dai. Model selection in batch policy optimization. arXiv preprint arXiv:2112.12320, 2021b.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.016443, 2020.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Advances in neural information processing systems, 33: 33:1264-1274 2020.
Gábor Lugosi and Andrew B Nobel. Adaptive model selection using empirical complexities. The Annals of Statistics, (11()))880-1866)) 1999.
Ajay Mandlekar, Danfei Xu, Josiah Wong, Soroush Nasiriany, Chen Wang, Rohun Kulkarni, Li Fei-Fei, Silvio Savarese, Yuke Zhu, and Roberto Martinn What matters in learning from offline human demonstrations for robot manipulation. arXiv preprint arXiv:2108.03200 2021.
Pascal Massart. Concentration inequalities and model selection: Ecole d' Etééé de Probabilités de Saint-Flour XXXIII-2003. Springer, 2007.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et Human- control through deep reinforcement learning. nature, 518(7550))55295533)) 2015.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.070:3: 2021.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
Vidya Muthukumar and Akshay Krishnamurthy. Universal and data- algorithms for model selection in linear contextual bandits. arXiv preprint arXiv:21/1.046883 2021.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019.
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances Neural Information Processing Systems, 33:10328 2020.
12

---

Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zoina, Alexander Novikov, Ziyu Wang, and Nando de Freitas. Hyperparameter selection for offline reinforcement learning. arXiv preprint arXiv:2007.09055 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Doina Precup. Eligibility traces for off- off-pooicy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
Takuma Seno and Michita Imai. d3rlpy: An offline deep reinforcement learning library. arXiv preprint arXiv:2111.03788,, 2021.
David Simchi-LLeii and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. Adaptive estimator selection for off off-policy evaluation. In International Conference on Machine Learning, pages 9196 9205. PMLR, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Shengpu Tang and Jenna Wiens. Model selection for offline reinforcement learning: Practical considerations for healthcare settings. In Machine Learning for Healthcare Conference, pages 2-35, PMLR, 2021.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pages 2139-2148. PMLR, 2016.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226, 2021.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.1188. 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 114404-11413, PMLR, 2021.
Tengyang Xie, Yifei Ma. and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning, Advances in neural information processing systems, 34:6683-6694, 2021.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online rl. In International Conference on Machine Learning, pages 12287-12297. PMLR, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. arXiv preprint arXiv:2202.04633 2022.
Siyuan Zhang and Nan Jiang, Towards hyperparameter- free policy selection for offline reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Introduction, Discussion,
and discussions assumptions and after every theorem statement.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The work is theoretical in nature.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of theoretical resultts [Yes] See preliminaries and before theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] See appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or a URL)? [Yes]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Empirical Results section and Appendix D.
(c) Did you report error bars (e.g.. with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix D.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "xD2opczUnqK", "reviewer": "Reviewer_QYVr", "summary": "This paper presents an algorithm for model selection with nested model classes when used with value function approximation for offline RL. The bound achieved by the proposed algorithm is minimax rate-optimal oracle inequalities (upto logarithmic factors). ", "questions": "Pretty much all my questions are summarized in the weaknesses above.", "limitations": "I'd recommend the authors consider any unintended implications of their paper's result, although, I do not see any specific limitations myself.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The problem and the related algorithm are new to my knowledge\n- The paper is well written\n- The theory is accompanied by some reasonable experimental support.\n\nWeaknesses:\n- The main issue I have with this paper is how do we obtain a set of nested function classes where such an ordering is actually satisfied? Clearly, the authors recognize this issue in footnote 3, and this, in a sense breaks much of what is developed in the paper since the paper posits the existence of nested model classes that satisfy the approximation error-statistical complexity trade-off. These issues are pretty much mirrored in existing works, where there is a need to select a model class for performing estimation and it is unclear how to tradeoff approximation and estimation error. I would recommend the authors discuss this in greater detail.\n- Another issue i see is while the authors stress schemes that achieve rate-optimality, the dependence on the approximation error appear to be sub-optimal, and this is the dominating term (particularly in the limit).\n- The experimental results are limited at best. I would recommend that these be expanded in scope to consider continuous control tasks (e.g. with D4RL benchmark suite) since many methods used for these tasks rely on variants of actor-critic methods. I do like the paper's result, although i am trying to understand if the authors could compensate for what appears to be non-trivial limitations in the problem setup through more extensive empirical studies.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b9B9yGaRvYo", "reviewer": "Reviewer_ewUJ", "summary": "This paper proposes an algorithm for offline reinforcement learning.", "questions": "What is the relation and difference of this paper and other works for offline RL, including [1], [2], and [3].\n\n[1]. Xie, Tengyang, et al. \"Bellman-consistent pessimism for offline reinforcement learning.\" Advances in neural information processing systems 34 (2021): 6683-6694.\n\n[2]. Zhan, Wenhao, et al. \"Offline reinforcement learning with realizability and single-policy concentrability.\" Conference on Learning Theory. PMLR, 2022.\n\n[3]. Uehara, Masatoshi, and Wen Sun. \"Pessimistic model-based offline reinforcement learning under partial coverage.\" arXiv preprint arXiv:2107.06226 (2021).\n", "limitations": "The relation and difference of their work and other works in offline RL is unmentioned.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: This paper provide an algorithm and upper bound its suboptimality.\n\nWeakness. The relation and difference of their work and other works in offline RL is unmentioned.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "W8iyrAAl2X", "reviewer": "Reviewer_cD9U", "summary": "This paper considers the model selection problem for offline RL where the learner is given a nested set of model classes and must choose which one to use completely offline without interacting with the environment. The paper extends previous work from the contextual bandit setting to the RL setting and achieves minimax optimal rates up to log factors for a novel algorithm ModBE. Importantly, ModBE relies on a one-sided generalization test where regressors from two models classes are compared on the same regression problem induced by the Bellman targets of the smaller model class in the nested ordering. Some empirical results are presented on small domains.", "questions": "Is it clear that we need to make assumption 1 or just that a simple assumption with one comparator policy is not sufficient? If we need assumption 1, how important are optimal rates if dependence on H is exponential regardless? Should we consider a more structured set of problems to avoid these issues and yield more practical insights?\n\nCan you provide empirical evidence where ModBE is clearly beneficial? Or even a toy problem where hold-out fails but ModBE succeeds?", "limitations": "The paper is sufficiently abstract that I think it is ok that it does not explicitly address ethical concerns in the main text.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The technique of applying the one-sided test on pairs of model classes for the same Bellman backup regression problem is clever and novel. The novel technique could be useful to the community as it is possible that the core idea could find uses in other problems around RL.\n\n2. The proofs seem to be correct, although I haven't checked everything in the appendix carefully.\n\nWeaknesses:\n\n1. In general it seems that one should expect C(\\mu) to be exponential in H. The lower bound from LTND21 says that dependence on a comparator policy is not possible, so the authors argue that this term is fundamental. But at that point, the main results of the paper seem to really only apply to short horizon problems. For any longish horizon, this constant will likely be enormous and the optimal rates may not really matter. It is still nice to have the optimal rates in n, but this seems like a serious issue that is sort of glossed over in the paper. It is possible that the problem as stated really is just too hard and that we should instead be considering more structured settings where the exponential lower bound could be avoided rather than proving bounds that are exponential.\n\n2. The experiments do not seem to show much benefit from the ModBE algorithm over the naive hold-out baseline. On the bandit and cartpole problems there is no noticeable difference at all. On mountain car ModBE seems slightly better, but never enough that the errorbars do not overlap with the baseline (and it seems that performance in the dataset is not good enough to learn a decent policy, no matter the model class). In my mind, these experiments cannot be seen as evidence of the usefulness of ModBE over the much simpler (both conceptually and implentation-wise) baseline.\n\n3. In practice, the ModBE algorithm itself has a hyperparameter in the form of the tolerance value. In the theory this can be set to some well-motivated value, but in practice it is often the case that those values will be overly conservative (as in most RL theory to practice conversions). For example, in the experiments the authors use a heuristic to set the tolerance based on pseudodimension bounds, but this may not be accessible with more realistic (i.e. larger neural net) model classes and then the parameter would need to be tuned. There is no discussion about sensistivity to this choice in practice and it seems like a serious issue for an algorithm that attempts to do model selection to potentially be hyperparameter sensitive itself.\n\nSummary:\n\nOverall, I think the paper studies an important problem and presents a clever algorithm and proof, but am wary of the significance of the contribution on a few levels: it seems that the assumptions effectively render the bound exponential in most realistic problems and from a practical perspective the paper does not provide clear evidence on the usefulness or robustness of the method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept