Year: 2021

Abstract:
Deep Reinforcement Learning (DRL) has demonstrated great potentials in solving sequential decision making problems in many applications. Despite its promising performance, practical gaps exist when deploying DRL in real-world scenarios. One main barrier is the over-fitting issue that leads to poor generalizability of the policy learned by DRL. In particular, for offline DRL with observational data, model selection is a challenging task as there is no ground truth available for performance demonstration, in contrast with the online setting with simulated environments. In this work, we propose a pessimistic model selection (PMS) approach for offline DRL with a theoretical guarantee, which features a provably effective framework for finding the best policy among a set of candidate models. Two refined approaches are also proposed to address the potential bias of DRL model in identifying the optimal policy. Numerical studies demonstrated the superior performance of our approach over existing methods.

heading: 1 INTRODUCTION
text: The success of deep reinforcement learning (Mnih et al., 2013; Henderson et al., 2018) (DRL) often leverages upon executive training data with considerable efforts to select effective neural architectures. Deploying online simulation to learn useful representations for DRL is not always realistic and possible especially in some high-stake environments, such as automatic navigation (Kahn et al., 2018; Hase et al., 2020), dialogue learning (Jaques et al., 2020), and clinical applications (Tang et al., 2020a). Offline reinforcement learning (Singh & Sutton, 1996; Levine et al., 2020; Agarwal et al., 2020) (OffRL) has prompted strong interests (Paine et al., 2020; Kidambi et al., 2020) to empower DRL toward training tasks associated with severe potential cost and risks. The idea of OffRL is to train DRL models with only logged data and recorded trajectories. However, with given observational data, designing a successful neural architecture in OffRL is often expensive (Levine et al., 2020), requiring intensive experiments, time, and computing resources.
Unlike most aforementioned applications with online interaction, Offline tasks for reinforcement learning often suffer the challenges from insufficient observational data from offline collection to construct a universal approximated model for fully capturing the temporal dynamics. Therefore, relatively few attempts in the literature have been presented for provide a pipeline to automate the development process for model selection and neural architecture search in OffRL settings. Here, model selection refers to selecting the best model (e.g., the policy learned by a trained neural network) among a set of candidate models (e.g. different neural network hyperparameters).
In this work, we propose a novel model selection approach to automate OffRL development process, which provides an evaluation mechanism to identify a well-performed DRL model given offline data. Our method utilizes statistical inference to provide uncertainty quantification on value functions trained by different DRL models, based on which a pessimistic idea is incorporated to select the best model/policy. In addition, two refined approaches are further proposed to address the possible biases of DRL models in identifying the optimal policy. In this work, we mainly focus on deep Q-network (Mnih et al., 2013; 2015) (DQN) based architectures, while our proposed methods can be extended to other settings. Figure 1 demonstrates the superior performance of the proposed pessimistic model selection (PMS) method in identifying the best model among 70 DRL models of different algorithms on one navigation task (See Appendix C for details), compared with the model selection method by (Tang & Wiens, 2021) which uses three offline policy evaluation (OPE)
estimates for validation. Specifically, based on the derived confidence interval of the OPE value for each candidate model, the final selected model by our PMS method is the one that has the largest lower confidence limit, which exactly has the largest true OPE value among all candidate models. In contrast, none of three OPE estimates used for model selection by Tang & Wiens (2021) can identify the best model due to the inevitable overfitting issue during the validation procedure.
To close this section, we summarize the contributions of this work as follows: • We propose a novel PMS framework, which targets finding the best policy from given candidate
models (e.g., neural architecture, hyperparameters, etc) with offline data for DQN learning. Unlike many existing methods, our approach essentially does not involve additional hyperparameter tuning except for two interpretable parameters.
• Leveraging asymptotic analysis in statistical inference, we provide uncertainty quantification on each candidate model, based on which our method can guarantee that the worst performance of finally selected model is the best among all candidate models. See Corollary 1 for more details.
• To address potential biases of candidate models in identifying the optimal policy, two refined approaches are proposed, one of which can be shown to have regret bounded by the smallest error bound among all candidate models under some technical conditions (See Corollary 2). To the best of our knowledge, this is the first model-selection method in offline DRL with such a guarantee.
• The numerical results demonstrate that the proposed PMS shows superior performance in different DQN benchmark environments.

heading: 2 RELATED WORK
text: Model Selection for Reinforcement Learning: Model selection has been studied in online decision-making environments (Fard & Pineau, 2010; Lee & Taylor, 2014). Searching nearly optimal online model is a critical topic for online bandits problems with limited information feed-backs. For linear contextual bandits, Abbasi-Yadkori et al. (2011); Chu et al. (2011) are aiming to find the best worst-case bound when the optimal model class is given. For model-based reinforcement learning, Pacchiano et al. (2020) introduces advantages of using noise augmented Markov Decision Processes (MDP) to archive a competitive regret bound to select an individual model with constraints for ensemble training. Recently, Lee et al. (2021) utilized an online algorithm to select a low-complexity model based on a statistical test. However, most of the previous model selection approaches are focused on the online reinforcement learning setting. Very few works including Farahmand & Szepesvári (2011); Paine et al. (2020); Su et al. (2020); Yang et al. (2020); Kuzborskij et al. (2021); Tang & Wiens (2021); Xie & Jiang (2021) are focused on the offline setting. In particular, (Su et al., 2020; Yang et al., 2020; Kuzborskij et al., 2021) focus on model selection for OPE problem. (Farahmand & Szepesvári, 2011; Xie & Jiang, 2021) select the best model/policy based on minimizing the Bellman error, while the first approach requires an additional tuning and latter does not. (Paine et al., 2020; Tang & Wiens, 2021) proposed several criteria to perform model selection in OffRL and mainly focused on numerical studies. In this work, we provide one of the first model selection approaches based on statistical inference for RL tasks with offline data collection.
Offline-Policy Learning: Training a DRL agent with offline data collection often relies on batchwise optimization. Batch-Constrained deep Q-learning (Fujimoto et al., 2019) (BCQ) is considered one OffRL benchmark that uses a generative model to minimize the distance of selected actions to the batch-wise data with a perturbation model to maximize its value function. Other popular OffRL
approaches, such as behavior regularized actor-critic (BRAC) (Wu et al., 2019), and random ensemble mixture (Agarwal et al., 2020) (REM) (as an optimistic perspective on large dataset), have also been studied in RL Unplugged (RLU) (Gulcehre et al., 2020) benchmark together with behavior cloning (Bain & Sammut, 1995; Ross & Bagnell, 2010) (BC), DQN, and DQN with quantile regression (Dabney et al., 2018) (QR-DQN). RLU suggests a naive approach based on human experience for offline policy selection, which requires independent modification with shared domain expertise (e.g., Atari environments) for tuning each baseline. Meanwhile, how to design a model selection algorithm for OffRL remains an open question. Motivated by the benefits and the challenges as mentioned earlier of the model selection for offline DRL, we aim to develop a unified approach for model selection in offline DRL with theoretical guarantee and interpretable tuning parameters.

heading: 3 BACKGROUND AND NOTATIONS
text: Consider a time-homogeneous Markov decision process (MDP) characterized by a tuple M = (S,A, p, r, γ), where S is the state space, A is the action space, p is the transition kernel, i.e., p(s′|s, a) is the probability mass (density) of transiting to s′ given current state-action (s, a), r is the reward function, i.e., E(Rt|St = s,At = a) = r(s, a) for t ≥ 0, and 0 ≤ γ < 1 is a discount factor. For simplifying presentation, we assume A and S are both finite. But our method can also be applied in continuous cases. Under this MDP setting, it is sufficient to consider stationary Markovian policies for optimizing discounted sum of rewards (Puterman, 1994). Denote π as a stationary Markovian policy mapping from the state space S into a probability distribution over the action space. For example, π(a|s) denotes the probability of choosing action a given the state value s. One essential goal of RL is to learn an optimal policy that maximizes the value function. Define V π(s) = ∑+∞ t=0 γ
tEπ[Rt|S0 = s] and then the optimal policy is defined as π∗ ∈ argmaxπ{V(π) , (1 − γ) ∑ s∈S V
π(s)ν(s)}, where ν denotes some reference distribution function over S. In addition, we denote Q-function asQπ(s, a) = ∑+∞ t=0 γ
tEπ(Rt|A0 = a, S0 = s) for s ∈ S and a ∈ A. In this work, we consider the OffRL setting. The observed data consist of N trajectories, corresponding to N independent and identically distributed copies of {(St, At, Rt)}t≥0. For any i ∈ {1, · · · , n}, data collected from the ith trajectory can be summarized by {(Si,t, Ai,t, Ri,t, Si,t+1)}0≤t<T , where T denotes the termination time. We assume that the data are generated by some fixed stationary policy denoted by b.
Among many RL algorithms, we focus on Q-learning type of methods. The foundation is the optimal Bellman equation given below.
Q∗(s, a) = E[Rt + γ max a′∈A Q∗(St+1, a ′) |St = s,At = a], (1)
where Q∗ is called optimal Q-function, i.e., Q-function under π∗. Among others, fitted q-iteration (FQI) is one of the most popular RL algorithms (Ernst et al., 2005). FQI leverages supervised learning techniques to iteratively solve the optimal Bellman equation (1) and shows competitive performance in OffRL.
To facilitate our model-selection algorithm, we introduce the discounted visitation probability, motivated by the marginal importance sampling estimator in (Liu et al., 2018). For any t ≥ 0, let pπt (s, a) denote the t-step visitation probability Pr
π(St = s,At = a) assuming the actions are selected according to π at time 1, · · · , t. We define the discounted visitation probability function as dπ(s, a) = (1 − γ) ∑ t≥0 γ
tpπt (s, a). To adjust the distribution from behavior policy to any target policy π, we use the discounted probability ratio function defined as
ωπ,ν(s, a) = dπ(s)π(a|s)
1 T ∑T−1 t=0 p b t(s, a) , (2)
where pbt(s, a) is the t-step visitation probability under the behavior policy b, i.e., Pr b(St = s,At = a). The ratio function ωπ,ν(s, a) is always assumed well defined. The estimation of ratio function is motivated by the observation that for every measurable function f defined over S ×A,
E[ 1 T T−1∑ t=0 ωπ,ν(St, At)(f(St, At)− γ ∑ a′∈A π(a′ | St+1)f(St+1, a′))]
= (1− γ)ES0∼ν [ ∑ a∈A π(a | S0)f(a, S0)], (3)
based on which several min-max estimation methods has been proposed such as (Liu et al., 2018; Nachum et al., 2019; Uehara & Jiang, 2019); We refer to (Uehara & Jiang, 2019, Lemma 1) for a formal proof of equation (3).
Finally, because our proposed model selection algorithm relies on an efficient evaluation of any target policy using batch data, we introduce three types of offline policy evaluation estimators in the existing RL literature. The first type is called direct method via estimating Q-function, based on the relationship that V(π) = (1 − γ) ∑ s∈S,a∈A π(a|s)Q(s, a)ν(s). The second type is motivated by the importance sampling (Precup, 2000). Based on the definition of ratio function, we can see V(π) = E[ 1T ∑T−1 t=0 ω
π,ν(St, At)Rt], from which a plugin estimator can be constructed. The last type of OPE methods combines the first two types of methods and construct a so-called doubly robust estimator (Kallus & Uehara, 2019; Tang et al., 2020b). This estimator is motivated by the efficient influence function of V(π) under a transition-sampling setting and the model that consists of the set of all observed data distributions given by arbitrarily varying the initial, transition, reward, and behavior policy distributions, subject to certain minimal regularity and identifiability conditions (Kallus & Uehara, 2019), i.e.,
1
T T−1∑ t=0 ωπ,ν(St, At)(Rt + γ ∑ a∈A π(a|St+1)Qπ(St+1, a)−Qπ(St, At))
+ (1− γ)ES0∼ν [ ∑ a∈A π(a|S0)Qπ(S0, a)]− V(π). (4)
A nice property of doubly robust estimators is that as long as either the Q-function Qπ(s, a) or the ratio function ωπ,ν(s, a) can be consistently estimated, the final estimator of V(π) is consistent (Robins et al., 1994; Jiang & Li, 2015; Kallus & Uehara, 2019; Tang et al., 2020b). Furthermore, a doubly robust estimator based on (4) can achieve semiparametric efficiency under the conditions proposed by (Kallus & Uehara, 2019), even if nuisance parameters are estimated via black box models such as deep neural networks. Therefore such an estimator is particularly suitable under the framework of DRL. Our proposed algorithm will rely on this doubly robust type of OPE estimator.

heading: 4 PESSIMISTIC MODEL SELECTION (PMS) FOR BEST POLICY
text: In this section, we discuss our pessimistic model selection approach. For the ease of presentation, we focus on the framework of (deep) Q-learning, where policy optimization is performed via estimating the optimal Q-function. While this covers a wide range of state-of-the-art RL algorithms such as FQI (Ernst et al., 2005), DQN (Mnih et al., 2013) and QR-DQN (Dabney et al., 2018), we remark that our method is not restricted to this class of algorithms.
Suppose we have total number of L candidate models for policy optimization, where each candidate model will output an estimated policy, say π̂l for 1 ≤ l ≤ L. Our goal is to select the best policy among L policies during our training procedure. Note that these L models can be different deep neural network architectures, hyper-parameters, and various classes of functions for approximating the optimal Q-function or policy class, etc.

heading: 4.1 DIFFICULTIES AND CHALLENGES
text: Given a candidate l among L models, we can apply for example FQI using the whole batch data Dn to learn an estimate of Q∗ as Q̂l and an estimated optimal policy π̂l defined as π̂l(a|s) ∈ argmaxa∈AQ̂l(s, a), for every s ∈ S . In order to select the final policy, one may use a naive greedy approach to choose some l̃ such that l̃ ∈ argmaxlES0∼ν [ ∑ a∈A π̂l(a|s)Q̂l(S0, a)], as our goal is to maximize V(π). However, using this criterion will lead to over-fitting. Specifically, due to the distributional mismatch between the behavior policy and target policies, which is regarded as a fundamental challenge in OffRL (Levine et al., 2020), we may easily overestimate Q-function, especially when some state-action pairs are not sufficiently visited in the batch data. This issue becomes more serious when we apply max-operator during our policy optimization procedure. Such observations have already been noticed in recent works, such as (Kumar et al., 2019; 2020; Paine et al., 2020; Yu et al., 2020; Tang & Wiens, 2021; Jin et al., 2021). Therefore, it may be inappropriate to use this criterion for selecting the best policy among L models.
One may also use cross-validation procedure to address the issue of over-fitting or overestimating Q-function for model selection. For example, one can use OPE approaches on the validate dataset to evaluate the performance of estimated policies from the training data set (see Tang & Wiens (2021) for more details). However, since there is no ground truth for the value function of any policies, the OPE procedure on the validation dataset cannot avoid involving additional tuning on hyperparameters. Therefore such a procedure may still incur a large variability due to the overfitting issue. In addition, arbitrarily splitting the dataset for cross-validation and ignoring the Markov dependent structure will cause additional errors, which should be seriously taken care of.

heading: 4.2 SEQUENTIAL MODEL SELECTION
text: In the following, we propose a pessimistic model selection algorithm for finding an optimal policy among L candidate models. Our goal is to develop an approach to estimate the value function under each candidate model during our policy optimization procedure with theoretical guarantee. The proposed algorithm is motivated by recent development in statistical inference of sequential decision making (Luedtke & Van Der Laan, 2016; Shi et al., 2020). The idea is to first estimate optimal Q-function Q∗, optimal policy π∗ and the resulting ratio function based on a chunk of data, and evaluate the performance of the estimated policy on the next chunk of data using previously estimated nuisance functions. Then we combine the first two chunks of data, perform the same estimation procedure and evaluation on the next chunk of data. The framework of MDP provides a nature way of splitting the data.
Specifically, denote the index of our batch dataset Dn as J0 = {(i, t) : 1 ≤ i ≤ n, 0 ≤ t < T}. We divide J0 into O number of non-overlapping subsets, denoted by J1, · · · , JO and the corresponding data subsets are denoted by D1, · · · ,DO. Without loss of generality, we assume these data subsets have equal size. We require that for any 1 ≤ o1 < o2 ≤ O, any (i1, t1) ∈ Jo1 and (i2, t2) ∈ Jo2 , either i2 6= i1 or t1 < t2. For 1 ≤ o ≤ O, denote the aggregate chunks of data as D̄o ={
(Si,t, Ai,t, Ri,t, Si,t+1), (i, t) ∈ J̄o = J1 ∪ · · · ∪ Jo } .
We focus on FQI algorithm for illustrative purpose and it should be noticed that our algorithm can be applied to other RL algorithms. Starting from the first chunk of our batch data, at the o-th step (o = 1, · · · , O − 1), for each candidate model l = 1, · · · , L, we apply FQI on D̄o to compute Q̂
(o) l as an estimate of optimal Q-function and obtain π̂ (o) l correspondingly such that π̂ (o) l (a|s) ∈ argmaxs∈AQ̂ (o) l (s, a) for every s ∈ S . Additionally, we compute an estimate of ratio function ωπ̂ (o) l ,ν using D̄o by many existing algorithms such as Nachum et al. (2019). Denote the resulting estimator as ω̂π̂ (o) l ,ν . The purpose of estimating this ratio function is to improve the efficiency and robustness of our value function estimation for each candidate model. Then we compute the estimated value function of π̂(o)l on Do+1 as
V̂Do+1(π̂ (o) l ) = (1− γ)ES0∼ν [ ∑ a0∈A π̂ (o) l (a0|S0)Q̂ (o) l (S0, a0)] (5)
+EDo+1 [ω̂ π̂ (o) l ,ν(S,A)(R+ γ ∑ a′∈A π̂ (o) l (a ′|S′)Q̂(o)l (S ′, a′)− Q̂(o)l (S,A))], (6)
where EDo+1 denotes the empirical average over the (o + 1) chunk of dataset and (S,A,R, S′) is one transition tuple in Do+1. While one can aggregate V̂Do+1(π̂ (o) l ) for 1 ≤ o ≤ (O− 1) to evaluate the performance of L models, the uncertainty of these estimates due to the finite sample estimation should not be ignored. Therefore, in the following, we derive an uncertainty quantification of our estimated value function for each candidate model, for performing model selection. Based on equation (4), (conditioning on D̄o), the variance of V̂Do+1(π̂ (o) l ) is
σ2(π̂ (o) l ) = E[{ω̂
π̂ (o) l ,ν(S,A)(R+ γ ∑ a′∈A π̂ (o) l (a ′|S′)Q̂(o)l (S ′, a′)− Q̂(o)l (S,A))} 2], (7)
where (S,A, S′) is a transition tuple with (S,A) follows some stationary distribution. See Assumption 1. Correspondingly we have an estimate defined as
σ̂2o+1(π̂ (o) l ) = EDo+1 [{ω̂
π̂ (o) l ,ν(S,A)(R+ γ ∑ a′∈A π̂ (o) l (a ′|S′)Q̂∗(o)l (S ′, a′)− Q̂∗(o)l (S,A))} 2]. (8)
The estimation procedure stops once we have used all our offline data and denote the final estimated policy as π̂l for each l = 1, · · · , L. Notice that π̂l = π̂(O)l . Finally, we compute the weighted average of all the intermediate value functions as our final evaluation of the estimated policy π̂l, i.e.,
V̂(π̂l) = ( O−1∑ o=1
1
σ̂o+1(π̂ (o) l )
)−1( O−1∑ o=1 V̂Do+1(π̂ (o) l ) σ̂o+1(π̂ (o) l ) ). (9)
In Section 5, we show that under some technical conditions, the following asymptotic result holds:√ nT (O − 1)/O ( V̂(π̂l)− V(π̂l) ) σ̂(l) =⇒ N (0, 1), (10)
where σ̂(l) = (O − 1)( ∑O−1 o=1 {σo+1(π̂ (o) l )}−1)−1, =⇒ refers to weak convergence when either n or T goes to infinity, and N (0, 1) refers to the standard normal distribution. Based on the asymptotic result in (10), we can construct a confidence interval for the value function of each policy π̂l. Given a confidence level α, for each l, we can compute U(l) = V̂(π̂l)− zα/2 √ O/nT (O − 1)σ̂(l), where zα/2 is (1 − α2 )-quantile of the standard normal distribution. Our final selected one is l̂ ∈ argmax1≤l≤L U(l).
The use of U(l) is motivated by the recent proposed pessimistic idea to address the overestimation issue of value (or Q) function in the OffRL setting. See Kumar et al. (2019; 2020); Jin et al. (2021); Xie et al. (2021); Uehara & Sun (2021); Zanette et al. (2021) for details. The final output of our algorithm is π̂l̂ and an outline of the proposed algorithm can be found in Algorithm 1. As we can see, our algorithm is nearly tuning free, which provides great flexibility in real-world applications. The only two adjustable parameters is O and α. The size of O balances the computational cost and the finite-sample accuracy of evaluating each candidate model. In specific, we can indeed show that the variance of the estimated value function by our algorithm can achieve the semi-parametric efficiency bound, which is best one can hope for. So in the asymptotic sense, the effect of O is negligible. In the finite-sample setting, we believe the performance will be discounted by a factor √ O − 1/O.
Therefore, if O is large enough, √ O − 1/O will have a mere effect on the performance. See Theorem 1. However, using large O will result in a large computational cost. As a sacrifice for the nearly tuning free algorithm, we need to apply OffRL algorithms O times for each candidate model. The parameter α determines how worst the performance of each policy we should use to evaluate each policy. See Corollary 1 for more insights.
Algorithm 1: Pessimistic Model Selection (PMS) for OffRL Input: Dataset Dn and L candidate models for estimating optimal Q-function and policy; We
divide Dn into non-overlapping subsets denoted by D1, · · · ,DO. We require that for any 1 ≤ o1 < o2 ≤ O, any (i1, t1) ∈ Jo1 and (i2, t2) ∈ Jo2 , either i2 6= i1 or t1 ≤ t2.
1 for l ∈ L do 2 for o = 1 to O − 1 do 3 For l ∈ L models, construct the optimal Q̂(o)l and π̂ (o) l using D̄o data subset. 4 Compute ω̂π̂ (o) l ,ν using D̄o by Nachum et al. (2019) and min-max solver for (3). 5 Compute V̂Do+1(π̂ (o) l ) and σ̂ 2 o+1(l) using Do+1 given in (5) and (8) respectively.
6 For l-th model, we compute U(l) = V̂(π̂l)− zα/2 √ nT (O − 1)/Oσ̂(l), where V̂(π̂l) and σ̂(l) are given in (9) and (10) respectively. 7 Pick l̂ = arg maxl U(l) as the selected model and run the algorithm on full dataset to obtain π̂l̂. 8 Return π̂l̂.

heading: 5 THEORETICAL RESULTS
text: In this section, we justify our asymptotic result given in (10). We use Op to denote the stochastic boundedness. Before that, we make several technical assumptions: Assumption 1 The stochastic process {At, St}t≥0 is stationary with stationary distribution p∞. Assumption 2 For every 1 ≤ l ≤ L and 1 ≤ o ≤ O, we have E|V(π̂(o)l )−V(π∗)| ≤ C0(nT/O)−κ, for some constant C0 and κ > 1/2.
Assumption 1 is standard in the existing literature such as (Kallus & Uehara, 2019). Assumption 2 is key to our developed asymptotic results developed. This assumption essentially states that all candidate models are good enough so that eventually their value functions will converge to that of the optimal one. This implies that there is no asymptotic bias in identifying the optimal policy. While this is reasonable thanks to the capability of deep neutral networks, which has demonstrated their empirical success in many RL applications, such an assumption could still be strong. In Section 6, we try to relax this assumption and provide two remedies for addressing possibly biased estimated policies. In addition, Assumption 1 also requires that the convergence rates of value functions under estimated policies are fast enough. This has been shown to hold under the margin condition on π∗, see e.g., (Hu et al., 2021) for more details. Assumption 3 For every 1 ≤ l ≤ L and 1 ≤ o ≤ O − 1, suppose E(S,A)∼p∞ |Q̂ (o) l (S,A) − Qπ̂ (o) l (S,A)|2 = Op{(nT/O)−2κ1} for some constant κ1 ≥ 0. In addition, Q̂(o)l is uniformly bounded almost surely. Assumption 4 For every 1 ≤ l ≤ L and 1 ≤ o ≤ O − 1, suppose E(S,A)∼p∞ |ω̂π̂ (o) l ,ν(S,A) − ωπ̂ (o) l ,ν(S,A)|2 = Op{(nT/O)−2κ2} for some constant κ2 ≥ 0. In addition, both ωπ̂ (o) l ,ν and ω̂π̂ (o) l ,ν are uniformly bounded above and below away from 0 almost surely. Assumption 5 For every 1 ≤ l ≤ L and 1 ≤ o ≤ O − 1, σ2(π̂(o)l ) and σ̂2o+1(π̂ (o) l ) are bounded above and below from 0 almost surely.
Assumptions 3 and 4 impose high-level conditions on two nuisance functions. Our theoretical results only require κ1 + κ2 > 1/2, which is a mild assumption. For example, if considered parametric models for both Q-function and ratio function, then κ1 = κ2 = 1/2. If considered nonparametric models for these two nuisance functions such as deep neural networks, then 1/4 < κ1, κ2 < 1/2 can be obtained under some regularity conditions. See Fan et al. (2020) and Liao et al. (2020); Uehara et al. (2021) for the convergence rates of Q-function and ratio function by non-parametric models respectively. In addition, Assumption 5 is a mild assumption, mainly for theoretical justification. Then we have the following main theorem as a foundation of our proposed algorithm. Theorem 1 Under Assumptions 1-5, we have
( √ nT (O − 1)/O ( V̂(π̂l)− V(π̂l) ) )/σ̂(l) =⇒ N (0, 1). (11)
Theorem 1 provides an uncertainty quantification of each candidate model used in policy optimization. Such uncertainty quantification is essential in OffRL as data are often limited. We highlight the importance of such results in Appendix A. A consequent result following Theorem 1 validates the proposed Algorithm 1:
Corollary 1 lim inf nT→∞
Pr(V(π̂l̂) ≥ max1≤l≤L V(π̂l)− 2zα/2 √ nT (O − 1)/Oσ̂(l)) ≥ 1−Lα under
Assumptions 1-5.
As can be seen clearly from Corollary 1 and the proposed PMS, with a large probability (by letting α small), we consider the worst performance of each candidate model π̂l in the sense of the lower confidence limit of the value function, and then select the best one among all models.

heading: 6 TWO REFINED APPROACHES
text: In this section, we relax Assumption 2 by allowing possibly non-negligible bias in estimating the optimal policy and introduce two refined approaches for addressing this issue. Instead of imposing Assumption 2, we make an alternative assumption below. Assumption 6 For every 1 ≤ l ≤ L, there exists B(l) such that max1≤o≤(O−1) |V(π̂ (o) l ) − V(π∗)| ≤ B(l) almost surely. Assumption 6 is a very mild assumption. It essentially states that the biases for all our intermediate value function estimates are bounded by some constant, which is much weaker than Assumption 2. In this case, the asymptotic results in (11) may not hold in general. Correspondingly, we have the following result. Theorem 2 Under Assumptions 1, 3-6, for every 1 ≤ l ≤ L, the following inequality holds.
lim inf nT→∞
Pr ( |V(π∗)− V̂(π̂l)| ≤ zα/2 √ O/nT (O − 1)σ̂(l) +B(l) ) ≥ 1− α. (12)
Motivated by Lepski’s principle (Lepski & Spokoiny, 1997) from nonparametric statistics and (Su et al., 2020) studying the model selection of OPE, we consider the following refined model-selection procedure to find the best policy. We first rank L candidate models in an non-increasing order based on the value of σ̂(l), i.e., for 1 ≤ i < j ≤ L, σ̂(i) ≥ σ̂(j). Then for i-th model, we construct an interval as I(l) = [V̂(π̂l)− 2zα/(2L) √ O/nT (O − 1)σ̂(l), V̂(π̂l) + 2zα/(2L) √ O/nT (O − 1)σ̂(l)]. Finally the optimal model/policy we choose is π̂î such that î = max{i : 1 ≤ i ≤ L,∩1≤j≤iI(j) 6= ∅}. To show this procedure is valid, we need to make one additional assumption. Assumption 7 There exists a ζ < 1 such that for 1 ≤ i ≤ L, B(i) ≤ B(i + 1) and ζσ̂(i) ≤ σ̂(i+ 1) ≤ σ̂(i) almost surely. This assumption is borrowed from Su et al. (2020). It typically assumes that after sorting our model based on σ̂(l), the bias of estimated policy is monotonically increasing and the standard deviation is monotonically deceasing but not too quickly. This is commonly seen when all candidate estimators exhibit some bias-variance trade-off phenomena. Define the following event
E = |V̂(π̂î)− V(π ∗)| ≤ 6(1 + ζ−1) min 1≤i≤L {B(i) + zα/(2L)
√ O/nT (O − 1)σ̂(i)}. (13)
Then we have the following theoretical guarantee for our refined procedure. Corollary 2 Under Assumptions 1, 3-7, we have lim inf
nT→∞ Pr(E) ≥ 1 − α. If we further assume
that for any δ > 0, with probability at least 1 − δ, for every 1 ≤ i ≤ L, |V(π̂i) − V̂(π̂i)| ≤ c(δ) log(L)σ̂(i)/ √ NT for some constant c(δ), then lim inf
nT→∞ Pr(Ē) ≥ 1− α− δ, where
Ē = |V(π̂î)− V(π ∗)| ≤ 3(1 + ζ−1) min
1≤i≤L {B(i) + (c(δ) log(L) + zα/(2L))
√ O/nT (O − 1)σ̂(i)}. (14)
The additional assumption (i.e., the high probability bound) in Corollary 2 can be shown to hold by the empirical process theory under some technical conditions (Van de Geer, 2000). Hence Corollary 2 provides a strong guarantee that the regret of the final selected policy is bounded by the smallest error bound among all L candidate policies. Note that Assumption 3 imposed here could be strong.
Another refined approach: Notice that the above refined approach indeed focuses on OPE estimates to select the best policy with regret warranty. The rough motivation behind is to find a policy that has the smallest estimation error to the optimal one. However, such procedure may not directly match the goal of maximizing the value function in OffRL. To relieve this issue , we can alternatively choose the final policy as π̂ˆ̂i such that ˆ̂i = argmax1≤i≤îV̂(π̂i)− 2zα/2 √ nT (O − 1)/Oσ̂(i), where the argmax is taken over î models. This approach can be viewed as a combination of PMS and the above refined approach. By adopting this approach, candidate models with large biases are firtly removed by the truncation on î. Then, we use the idea of PMS to select the best model having the best worst performance among the remaining candidates. Unfortunately, we do not have theoretical guarantee for this combined approach.

heading: 7 EXPERIMENTAL RESULTS
text: We select six DQN environments (E1 to E6) from open-source benchmarks (Brockman et al., 2016; Juliani et al., 2018) to conduct numerical experiments, as shown in Fig. 5 of Appendix C. These tasks of deployed environments cover different domains that include tabular learning (Fig 5(a)); automatic navigation in a geometry environment with a physical ray-tracker (Fig 5(b)); Atari digital gaming (Fig 5(c) and (d)), and continuous control (Fig 5(e) and (f)). We provide detailed task description and targeted reward for each environment in Appendix C.
Experiment setups. To evaluate the performance of PMS with DQN models in offRL, we choose different neural network architectures under five competitive DRL algorithms including DQN by (Mnih et al., 2013; 2015), BCQ by (Fujimoto et al., 2019), BC by (Bain & Sammut, 1995; Ross & Bagnell, 2010), BRAC by (Wu et al., 2019) from RLU benchmarks, and REM by (Agarwal et al., 2020). Within each architecture, 70 candidate models are created by assigning different hyperparameters and training setups. See Appendix C.1 for details. We then conduct performance evaluation of different OffRL model selection methods on these generated candidate models.
Evaluation procedure. We utilize validation scores from OPE for each model selection algorithm, which picks the best (or a good) policy from the candidate set of size L based on its own criterion.
Regret is used as the evaluation metric for each candidate. The regret for model l is defined as V (πl∗) − V (π̂l), where l∗ = arg maxl′=1...L V (πl′) corresponds to the candidate policy with the best OPE validation performance. In our implementation, we treat πl∗ as π∗, the oracle but unknown best possible policy. A small regret is desirable after model selection. Note the optimal regret is not zero since we can only use data to obtain π̂l instead of πl for each model. We provide additional top-k regret and precision results from Figure 6 to 16 in Appendix C.
Performance comparison. As highlighted in Fig. 1 in the introduction, we report estimated OPE values by different model selection approaches, i.e. PMS and three methods by (Tang & Wiens, 2021), versus the true OPE values. In this experiment, we consider 70 DQN models under the above mentioned five DRL algorithms, i.e., 14 models are considered for each architecture. We use fewer models for each DRL algorithm mainly for clear presentation. By using the confidence interval constructed by our PMS procedure, our method is able to correctly select the top models, while the other three methods fail. To further investigate the performance of PMS, we implement model selection among 70 models within each DRL algorithm separately. Fig. 2 shows the box plots of averaged regret over six environments after OPE per neural network architecture. Each subfigure contains results from one particular DRL algorithm with different hyperparameters or training setups. The left box plot refers to the regrets of all 70 models and the right one represents the regrets of top 10% models selected by the proposed PMS method. Note that the right box plot is a subset of the left one. The results show that our proposed PMS successfully helps to select models with the best policies and improve the average regret by a significant margin. In particular, PMSREM-based models attain the lowest regrets, due to the benefit from its ensemble process. Detailed results for each environment is given in Appendix C.
Sensitivity analysis. Fig. 3 compares different selection algorithms with varying training data size. PMS outperforms others across all scales, and larger number of episodes gives smaller variation and lower sensitivity.
PMS algorithm with refinements. We replicate our experiments on in the offline navigation task in E2 (Banana Collector) for 30 times and report regrets of top 10% models selected by PMS and two refinements in Fig. 4. As we can see, while the overall performances of the proposed three model selection methods are sim-
ilar, two refined approaches have better regrets than PMS in terms of median, demonstrating their promising performances in identifying the best model. OPE results have been also evaluated also in DRL tasks with E1 and E3 to E6, where the refinement algorithms (PMS R1/R2) have only a small relative ± 0.423 % performance difference compared to its original PMS setups.

heading: 8 CONCLUSION
text: We propose a new theory-driven model selection framework (PMS) for offline deep reinforcement learning based on statistical inference. The proposed pessimistic mechanism is warrants that the worst performance of the selected model is the best among all candidate models. Two refined approaches are further proposed to address the biases of DRL models. Extensive experimental results on six DQN environments with various network architectures and training hyperparameters demonstrate that our proposed PMS method consistently yields improved model selection performance over existing baselines. The results suggest the effectiveness of PMS as a powerful tool toward automating model selection in offline DRL.

heading: A COMMENTS ON ASYMPTOTIC RESULTS
text: We remark here that all theoretical justification in this paper is based on asymptotics. It might be possible to investigate finite sample regimes when one has an exact confidence interval instead of (11) or a non-asymptotic bound. However, having an exact confidence interval might require some model specification of the value function, and using non-asymptotic bounds might require additional tuning steps (e.g., constants in many concentration inequalities), which is beyond the scope of this paper. In addition, as seen from our empirical evaluations below, with a relatively large sample size, the proposed model selection approach performs well.

heading: B TECHNICAL PROOFS
text: Notations: The notation ξ(N) . θ(N) (resp. ξ(N) & θ(N)) means that there exists a sufficiently large (resp. small) constant c1 > 0 (resp. c2 > 0) such that ξ(N) ≤ c1θ(N) (resp. ξ(N) ≥ c2θ(N)) for some sequences θ(N) and ξ(N) related to N . In the following proofs, N often refers to some quantity related to n and T .
Lemma 1 and its proof : Let J denotes some index of our batch data Dn. Define
φ(J,Qπ, ωπ,ν , π) = 1 |J | ∑
(i,t)∈J
ωπ,ν(Si,t, At) ( Ri,t + γ
∑ a′∈A π(a′|Si,t+1)Qπ(Si,t+1, a′)−Qπ(Si,t, Ai,t)
) ,
where |J | is the cardinality of the index set J , e.g., |Jo| = nTO for every 1 ≤ o ≤ O. Then we have the following Lemma 1 as an intermediate result to Theorem 1.
Lemma 1 Under Assumptions 1 and 3-5, for every 1 ≤ l ≤ L and 1 ≤ o ≤ O − 1, the following asymptotic equivalence holds.√
nT
O
{ V̂Do+1(π̂ (o) l )− V(π̂ (o) l ) } = √ nT
O φ(J,Qπ̂
∗(o) , ωπ̂ (o) l ,ν , π̂ (o) l ) + op(1), (15)
where op(1) refers to a quantity that converges to 0 as n or T goes to infinity.
The proof is similar to that of Theorem 7 in Kallus & Uehara (2019). First, notice that√ nT
O
{ V̂Do+1(π̂ (o) l )− V(π̂ (o) l ) }
=
√ nT
O
{ φ(J, Q̂π̂ ∗(o) , ω̂π̂ (o) l ,ν , π̂
(o) l )− φ(J,Q π̂∗(o) , ωπ̂ (o) l ,ν , π̂ (o) l )
+ (1− γ)ES0∼ν [ ∑ a∈A π̂ (o) l (a|S0)Q π̂ (o) l (S0, a)]− (1− γ)ES0∼ν [ ∑ a∈A π̂ (o) l (a|S0)Q π̂ (o) l (S0, a)]
}
+
√ nT
O φ(J,Qπ̂
∗(o) , ωπ̂ (o) l ,ν , π̂ (o) l ).
Then it suffices to show the term in the first bracket converges to 0 faster than √ nT . Notice that{
φ(J, Q̂π̂ ∗(o) , ω̂π̂ (o) l ,ν , π̂ (o) l )− φ(J,Q π̂∗(o) , ωπ̂ (o) l ,ν , π̂ (o) l )
+ (1− γ)ES0∼ν [ ∑ a∈A π̂ (o) l (a|S0)Q π̂ (o) l (S0, a)]− (1− γ)ES0∼ν [ ∑ a∈A π̂ (o) l (a|S0)Q π̂ (o) l (S0, a)] } =E1 + E2 + E3,
where
E1 = O
nT ∑ (i,t)∈Jo+1 (ω̂π̂ (o) l ,ν(Si,t, Ai,t)− ωπ̂ (o) l ,ν(Si,t, Ai,t))(Ri,t −Qπ̂ (o) l (Si,t, Ai,t)
+γ ∑ a∈A π̂ (o) l (a|Si,t+1)Q π̂ (o) l (Si,t+1, a)),
E2 = O
nT ∑ (i,t)∈Jo+1 ωπ̂ (o) l ,ν(Si,t, Ai,t)(Q̂ π̂ (o) l (Si,t, Ai,t)−Qπ̂ (o) l (Si,t, Ai,t)
+γ ∑ a∈A π̂ (o) l (a|Si,t+1)(Q̂ π̂ (o) l (Si,t+1, a)−Qπ̂ (o) l (Si,t+1, a))),
and
E3 = O
nT ∑ (i,t)∈Jo+1 (ω̂π̂ (o) l ,ν(Si,t, Ai,t)− ωπ̂ (o) l ,ν(Si,t, Ai,t))(Q̂ π̂ (o) l (Si,t, Ai,t)−Qπ̂ (o) l (Si,t, Ai,t)
+γ ∑ a∈A π̂ (o) l (a|Si,t+1)(Q̂ π̂ (o) l (Si,t+1, a)−Qπ̂ (o) l (Si,t+1, a))).
Next, we bound each of the above three terms. For term E1, it can be seen that
E[E1|J̄o] = 0.
In addition, by Assumptions 3 and 4, we can show
Var[E1] = E[Var(E1|J̄o)] . O
nT (nT/O)−2κ2 ,
where the inequality is based on that each item in E3 is uncorrelated with others. Then by Markov’s inequality, we can show
|E1| = Op(( O
nT )−1/2−κ2).
Similarly, we can show
|E2| = Op(( O
nT )−1/2−κ1).
For term (E3), by Cauchy Schwarz inequality and similar arguments as before, we can show
|E3| = Op(( O
nT )−(κ2+κ1)).
Therefore, as long as (κ2 + κ1) > 1/2, we have E1 + E2 + E3 = o( √ O/nT ), which concludes our proof.
Proof of Theorem 1 We aim to show that√ nT (O − 1)/O ( V̂(π̂l)− V(π̂l) ) σ̂(l) =⇒ N (0, 1).
It can be seen that√ nT (O − 1)/O ( V̂(π̂l)− V(π̂l) ) σ̂(l) = √ nT O(O − 1) ( O−1∑ o=1 V̂Do+1(π̂ (o) l )− V(π̂l) σ̂o+1(π̂ (o) l ) )
=
√ nT
O(O − 1) ( O−1∑ o=1 V̂Do+1(π̂ (o) l )− V(π̂ (o) l ) σ̂o+1(π̂ (o) l ) )
+
√ nT
O(O − 1) ( O−1∑ o=1 V(π̂(o)l )− V(π̂l) σ̂o+1(π̂ (o) l ) ) .
Define
φ(J,Qπ, wπ, π) = 1 |J | ∑
(i,t)∈J
wπ,ν(Si,t, At) ( Ri,t + γ
∑ a′∈A π(a′|Si,t+1)Qπ(S9,t+1, a′)−Qπ(Si,t, Ai,t)
) ,
where |J | is the cardinality of the index set J , i.e., |J | = nTO . Then by Lemma 1, we show that√ nT
O
V̂Do+1(π̂ (o) l )− V(π̂ (o) l )
σ̂o+1(π̂ (o) l )
=
√ nT
O
φ(Jo+1, Q π̂ (o) l , wπ̂ (o) l , π̂ (o) l )
σ̂o+1(π̂ (o) l )
+ op(1). (16)
If we can show that
max 1≤o≤(O−1) ∣∣∣∣∣ σ̂o+1(π̂(o)l )σo+1(π̂(o)l ) − 1 ∣∣∣∣∣ = op(1),
which will be shown later, then by Slutsky theorem, we can show that√ nT
O(O − 1) ( O−1∑ o=1 V̂Do+1(π̂ (o) l )− V(π̂ (o) l ) σ̂o+1(π̂ (o) l ) )
=
√ nT
O(O − 1) ( O−1∑ o=1 φ(Jo+1, Q π̂ (o) l , wπ̂ (o) l , π̂ (o) l ) σo+1(π̂ (o) l ) ) ︸ ︷︷ ︸
(I)
+op(1).
For (I), we can see that
(I) =
√ O
nT (O − 1) ( O−1∑ o=1 ∑ (i,t)∈Jo+1 wπ̂ (o) l ,ν(Si,t, Ai,t)(Ri,t (17)
+ γ ∑ a′∈A π̂ (o) l (a ′|Si,t+1)Qπ̂ (o) l (Si,t+1, a ′)−Qπ̂ (o) l (Si,t, Ai,t))/σo+1(π̂ (o) l )). (18)
By the sequential structure of our proposed algorithm, (I) forms a mean zero martingale. Then we use Corollary 2.8 of (McLeish, 1974) to show its asymptotic distribution. First of all, by the uniformly bounded assumption on Q-function, ratio function and the variance, we can show that√
O
nT (O − 1) max 1≤o≤(O−1) max (i,t)∈J0 ∣∣∣∣∣wπ̂(o)l ,ν(Si,t, Ai,t)(Ri,t + γ ∑ a′∈A π̂ (o) l (a ′|Si,t+1)Qπ̂ (o) l (Si,t+1, a ′)−
Qπ̂ (o) l (Si,t, Ai,t))/σo+1(π̂ (o) l ) ∣∣∣ = op(1).
Next, we aim to show that
O
nT (O − 1) ∣∣∣∣∣∣( O−1∑ o=1 ∑ (i,t)∈Jo+1 {wπ̂ (o) l ,ν(Si,t, Ai,t)(Ri,t (19)
+γ ∑ a′∈A π̂ (o) l (a ′|Si,t+1)Qπ̂ (o) l (Si,t+1, a ′)−Qπ̂ (o) l (Si,t, Ai,t))}2/σ2o+1(π̂ (o) l ))− 1 ∣∣∣∣∣ = op(1). Notice that the left hand side of the above is bounded above by
O
nT max 1≤o≤(O−1) ∣∣∣∣∣∣( ∑
(i,t)∈Jo+1
{wπ̂ (o) l ,ν(Si,t, Ai,t)(Ri,t (20)
+γ ∑ a′∈A π̂ (o) l (a ′|Si,t+1)Qπ̂ (o) l (Si,t+1, a ′)−Qπ̂ (o) l (Si,t, Ai,t))}2/σ2o+1(π̂ (o) l ))− 1 ∣∣∣∣∣ . (21)
Because, for each 1 ≤ o ≤ (O − 1),
O
nT ( ∑ (i,t)∈Jo+1 {wπ̂ (o) l ,ν(Si,t, Ai,t)(Ri,t (22)
+γ ∑ a′∈A π̂ (o) l (a ′|Si,t+1)Qπ̂ (o) l (Si,t+1, a ′)−Qπ̂ (o) l (Si,t, Ai,t))}2 − E[{wπ̂ (o) l ,ν(S,A)(R (23)
+γ ∑ a′∈A π̂ (o) l (a ′|S′)Qπ̂ (o) l (S′, a′)−Qπ̂ (o) l (S,A))}]/σ2o+1(π̂ (o) l ))
} , (24)
forms a mean zero martingale, we apply Freedman’s inequality in (Freedman, 1975) with Assumptions 3-5 to show it is bounded by Op( √ O nT ). Applying union bound shows (19) is op(1) and furthermore consistency of σ̂(π̂l) in (16) holds. Then we apply the martingale central limit theorem to show √
nT
O(O − 1) ( O−1∑ o=1 φ(Jo+1, Q π̂ (o) l , wπ̂ (o) l , π̂ (o) l ) σo+1(π̂ (o) l ) ) =⇒ N (0, 1).
The remaining is to show √ nT
O(O − 1) ( O−1∑ o=1 V(π̂(o)l )− V(π̂l) σ̂o+1(π̂ (o) l ) ) is asymptotically negligible. Consider
E ∣∣∣V(π̂(o)l )− V(π̂l)∣∣∣ (25)
≤E ∣∣∣V(π̂(o)l )− V(π∗l )∣∣∣+ E |V(π̂l)− V(π∗l )| (26)
≤E ∣∣∣V(π̂(o)l )− V(π∗l )∣∣∣+ E |V(π̂l)− V(π∗l )| (27)
≤(nTo)−κOκ + (nT )−κ, (28)
where we use Assumption 2 for the last inequality. Summarizing together, we can show that√ nT
O(O − 1) E ∣∣∣∣∣ O−1∑ o=1 V(π̂(o)l )− V(π̂l) ∣∣∣∣∣ ≤ √ nT
O(O − 1) O−1∑ o=1 (nTo)−κOκ +
√ nT (O − 1)
O (nT )−κ
≤
√ nTO2
O(O − 1) O−1∑ o=1 (nT )−κ +
√ nT (O − 1)
O (nT )−κ
=o(1), where we obtain the second inequality by that ∑O−1 o=1 o −κ ≤ 1 + ∫ O 1 o−κdo . O1−κ. In the last inequality, we use κ > 1 in Assumption 2. Then Markov inequality gives that√ nT
O(O − 1) ( O−1∑ o=1 V(π̂(o)l )− V(π̂l) ) = op(1).
Moreover, by Assumption 5 that inf1≤o≤O−1 σ̂o+1(π̂ (o) l ) ≥ c for some constant c > 0, we can
further show that √ nT
O(O − 1) ( O−1∑ o=1 V(π̂(o)l )− V(π̂l) σ̂o+1(π̂ (o) l ) ) = op(1),
which completes our proof.
Proof of Corollary 1 Denote the sets El = {|V(π̂l) − V̂(π̂l)| ≤ û(l)}, l = 1, . . . , L, where û(l) = zα/2 √ nT (O − 1)/Oσ̂(l). Note that lim infnT→∞ Pr(∩Lj=1Ej) ≥ 1− Lα and
Pr(V(π̂l̂) ≥ max1≤l≤LV(π̂l)− 2û(l))
= Pr(V(π̂l̂)− V̂(π̂l̂) + V̂(π̂l̂) ≥ max1≤l≤LV(π̂l)− V̂(π̂l)− 2û(l) + V̂(π̂l))
≥Pr(V(π̂l̂)− V̂(π̂l̂) + V̂(π̂l̂) ≥ max1≤l≤LV(π̂l)− V̂(π̂l)− 2û(l) + V̂(π̂l)| ∩ L j=1 Ej) Pr(∩Lj=1Ej)
≥Pr(V̂(π̂l̂)− û(l̂) ≥ max1≤l≤L V̂(π̂l)− û(l)| ∩ L j=1 Ej) Pr(∩Lj=1Ej)
= Pr(∩Lj=1Ej),
where the last inequality holds because given the event ∩Lj=1Ej , one has −û(l̂) ≤ V(π̂l̂) − V̂(π̂l̂) and V(π̂l)− V̂(π̂l) ≤ û(l) for any l. This completes the proof by taking lim inf on both sides. Proof of Theorem 2 To show the results in Theorem 2, it can be seen that∣∣∣∣∣∣ √ nT (O − 1)/O ( V̂(π̂l)− V(π∗) ) σ̂(l) ∣∣∣∣∣∣ ≤ ∣∣∣∣∣ √ nT O(O − 1) ( O−1∑ o=1 V̂Do+1(π̂ (o) l )− V(π̂ (o) l ) σ̂o+1(π̂ (o) l )
)∣∣∣∣∣ + √ nT
O(O − 1) ( O−1∑ o=1 V(π̂(o)l )− V(π∗) σ̂o+1(π̂ (o) l ) )
≤ ∣∣∣∣∣ √ nT O(O − 1) ( O−1∑ o=1 V̂Do+1(π̂ (o) l )− V(π̂ (o) l ) σ̂o+1(π̂ (o) l ) )∣∣∣∣∣︸ ︷︷ ︸ (I)
+B(l)
√ nT
O(O − 1) ( O−1∑ o=1
1
σ̂o+1(π̂ (o) l )
) .
Then by results in the proof of Theorem 1, we can show that
lim nT→∞ Pr((I) > zα/2) = α. (29)
This implies that
lim inf nT→∞
Pr ( |V(π∗)− V̂(π̂l)| ≤ zα/2 √ O/nT (O − 1)σ̂(l) +B(l) ) (30)
≥ lim nT→∞ Pr((I) ≤ zα/2) = 1− α, (31)
which concludes our proof.
Proof of Corollary 2: We mainly show the proof of the second claim in the corollary, based on which the first claim can be readily seen. Define an event E such that 1 ≤ l ≤ L, |V(π̂l)−V̂(π̂l)| ≤ c(δ) log(L)σ̂(i)/ √ NT and |V(π∗)− V̂(π̂l)| ≤ zα/(2L) √ O/nT (O − 1)σ̂(l) +B(l). Based on the assumption given in Corollary 2 and Theorem 2, we have lim inf nT→∞
P (E) ≥ 1−δ−α. In the following, we suppose event E holds.
Inspired by the proofs of Corollary 1 in (Mathé, 2006) and Theorem 3 of (Su et al., 2020), we define l̃ = max{l : B(l) ≤ u1(l) + u2(l)}, where u1(l) = zα/(2L) √ O/nT (O − 1)σ̂(l). Let u2(l) = c(δ) log(L)σ̂(i)/ √ NT . By Assumption 7, for l ≤ l̃,
B(l) ≤ B(l̃) ≤ u1(l̃) ≤ u1(l),
which further implies that for any l ≤ l̃,
|V̂(π̂l)− V(π∗)| ≤ B(l) + u1(l) ≤ 2u1(l).
Then V(π∗) ∈ I(l) based on the construction of I(l) for all l ≤ l̃. In addition, we have for l ≤ l̃
|V(π̂l)− V(π∗)| ≤ 2u1(l) + u2(l), (32)
by triangle inequality and event E. Since I(l) share at least one common element for 1 ≤ l ≤ l̃, we have î ≥ l̃. Moreover, there must exist an element x such that x ∈ I(l̃)∩ I (̂i), where |V̂(π̂l̃)− x| ≤ u1(l̃) and |V̂(π̂î)− x| ≤ u1(̂i). This indicates that
|V̂(π̂î − V(π ∗)| ≤ |V̂(π̂î)− x|+ |V̂(π̂l̃)− x|+ |V̂(π̂l̃)− V(π ∗)| (33) ≤ u1(̂i) + 2u1(l̃) ≤ 3u1(l̃), (34)
by again triangle inequality and Assumption 7, and
|V(π̂î)− V(π ∗)| ≤ u2(̂i) + 3u1(l̃) ≤ u2(l̃) + 3u1(l̃), (35)
by event E and Assumption 7. Define l∗ = min{l : B(l) + u1(l) + u2(l)}. Then following the similar proof of (Su et al., 2020), we consider two cases:
Case 1: If l∗ ≤ l̃, then we have
u2(l̃) +B(l̃) + u1(l̃) ≤ 2u1(l∗) + u2(l∗) ≤ 2u1(l∗) + 2B(l∗) + u2(l∗),
where we use Assumption 7.
Case 2: If l∗ > l̃, then we have
ζ(u2(l̃) + u1(l̃)) ≤ (u2(l̃ + 1) + u1(l̃ + 1)) ≤ B(l̃ + 1) ≤ B(l∗),
where we use Assumption 7. This implies that
u2(l̃) + u1(l̃) +B(l̃) ≤ (1 + 1/ζ)B(l∗).
Combining two cases, we can show that
u2(l̃) + u1(l̃) +B(l̃) ≤ (1 + 1/ζ)(B(l∗) + u1(l∗) + u2(l∗)),
as ζ < 1. Together with (33), we have
|V(π̂î)− V(π ∗)| ≤ u2(̂i) + 3u1(l̃) ≤ 3(1 + 1/ζ)(B(l∗) + u1(l∗) + u2(l∗)), (36)
which concludes our proof.

heading: C MORE DETAILS ON DQN ENVIRONMENTS
text: We introduce our deployed DQN environments in this section, which included four environments with discrete action (E1 to E4) and two environments (E5 to E6) with continuous action. These environments cover wide applications, including tabular learning (E1), navigation to a target object in a geometrical space (E2), digital gaming (E3 to E4), and continuous control (E5 to E6).
E1: Frozen Lake: The Frozen Lake is a maze environment that manipulates an agent to walk from a starting point (S) to a goal point without failing into the hole (H). We use FrozenLake-v0 from OpenAI Gym (Brockman et al., 2016) as shown in Fig 5(a). We provide top-5 regret and precision results shown in Figure 6 and 7.
E2: Banana Collector: The Banana collector is one popular 3D-graphical navigation environment that compresses discrete actions and states as an open source DQN benchmark from Unity 1 ML-Agents v0.3.(Juliani et al., 2018). The DRL agent controls an automatic vehicle with 37 dimensions of state observations including velocity and a ray-based perceptional information from objects around the agent. The targeted reward is 12.0 points by accessing correct yellow bananas (+1) and avoiding purple bananas (−1) in first-person point of view as shown in Fig 5(b). We provide the related top-5 regret and precision results shown in Figure 8 and 9.
E3: Pong: Pong is one Atari game environment from OpenAI Gym (Brockman et al., 2016) as shown in Fig 5(c). We provide its top-5 regret and precision results shown in Figure 10 and 11.
E4: Breakout: Breakout is one Atari game environment from OpenAI Gym (Brockman et al., 2016) as shown in Fig 12(d). We provide the related top-5 regret and precision results shown in Figure 12 and 13.
1https://www.youtube.com/watch?v=heVMs3t9qSk
E5: HalfCheetah-v1: Halfcheetah is a continuous action and state environment to control agent with monuments made by MuJoCo simulators as shown in Fig 5(e). We provide the related top-5 regret and precision results shown in Figure 14 and 15.
E6: Walker2d-v1: Walker2d-v1 is a continuous action and state environment to control agent with monuments made by MuJoCo simulators as shown in Fig 5(f). We provide the related top-5 regret and precision results shown in Figure 16 and 17.
C.1 HYPER-PARAMETERS INFORMATION
We select a total of 70 DQN based models for each environment. We will open source the model and implementation for future studies. Table 1, Table 2, and Table 3 summarize their hyper-parameter and setups. In addition, Figure 18 and Figure 19 provide ablation studies on different scales of α and O selection in PMS experiments for the deployed DRL navigation task (E2). From the experimental results, a more pessimistic α (e.g., 0.001) is associated with a slightly better attained top-5 regret. Meanwhile, the selection of O does not produce much different performance on selected policies but slightly affects the range of the selected policies.
BROADER IMPACT
There are also some limitations of the proposed PMS as one of the preliminary attempts on model selection for offline reinforcement learning. When the benchmarks environments (excluded Atari games) are based on simulated environments to collect the true policy (Barth-Maron et al., 2018; Siegel et al., 2019), more real-world-based environments could be customized and studied in future works. For example, one experimental setup needs to be carefully controlled in clinical settings (Tang & Wiens, 2021) or resilience-oriented (Yang et al., 2021) reinforcement learning.

Review summaries:
This paper considers the model selection problem in offline RL and proposes a new procedure called pessimistic model selection (PMS) that estimates performance lower bound for each candidate policy. Theoretical results show that under certain assumptions PMS can identify the best candidate policy with high probability. The proposed approach is compared to three common OPE methods used in Tang & Wiens 2021 and shows favorable performance on 6 RL domains. 

This paper proposed a new algorithm for model-section in offline RL based on adding the pessimism principle on top of existing OPE algorithms. Under strong assumptions, the paper provides an asymptotic convergence result for the proposed algorithm. It also provides empirical experiments demonstrating that the proposed algorithm outperforms existing baselines.

The paper studies the model selection problem in offline reinforcement learning (ORL). The model selection of ORL is challenging due to insufficient observational data from offline collection. The paper proposes a novel model selection approach to automate ORL development process and to identify a well-performed model given offline data. The proposed pessimistic model selection (PMS) method leverages an uncertainty quantification on value functions and a pessimistic idea. Some experiments show the superior performance of the proposed model selection method.