When is Offline Hyperparameter Selection Feasible for Reinforcement Learning?
Authors: Vincent Liu
Prabhat Nagarajan
Andrew Patterson
Martha White
Venue: Submitted to ICLR 2023 (2023)
Keywords: Offline policy selection
offline reinforcement learning
off-policy policy evaluation

Abstract: Hyperparameter selection is a critical procedure before deploying reinforcement learning algorithms in real-world applications. However, hyperparameter selection prior to deployment requires selecting policies offline without online execution, which is a significant challenge known as offline policy selection. As yet, there is little understanding about the fundamental limitations of the offline policy selection problem. To contribute to our understanding of this problem, in this paper, we investigate when sample efficient offline policy selection is possible. As off-policy policy evaluation (OPE) is a natural approach for policy selection, the sample complexity of offline policy selection is therefore upper-bounded by the number of samples needed to perform OPE. In addition, we prove that the sample complexity of offline policy selection is also lower-bounded by the sample complexity of OPE. These results imply not only that offline policy selection is effective when OPE is effective, but also that sample efficient policy selection is not possible without additional assumptions that make OPE effective. Moreover, we theoretically study the conditions under which offline policy selection using Fitted Q evaluation (FQE) and the Bellman error is sample efficient. We conclude with an empirical study comparing FQE and Bellman errors for offline policy selection.

Under review as a conference paper at ICLR 2023
WHEN IS OFFLINE POLICY SELECTION FEASIBLE FOR REINFORCEMENT LEARNING?
Anonymous authors Paper under double-blind review
ABSTRACT
Hyperparameter selection and algorithm selection are critical procedures before deploying reinforcement learning algorithms in real-world applications. How- ever, dggorthm-hyperppramne
selection prior to deployment requires selecting policies offline without online execution, which is a significant challenge known as offline policy selection. As yet, there is little understanding about the funda- mental limitations of the offline policy selection problem. To contribute to our understanding of this problem, in this paper, we investigate when sample efficient offline policy selection possible. As off-policy policy evaluation (OPE) is a natural approach for policy selection, the sample complexity of offline policy se- lection is therefore upper-bounded by the number of samples needed to perform OPE. In addition, prove that the sample complexity of offline policy selection is also only that offline policy selection is effective when OPE is effective, but also that sample efficient policy selection is not possible without additional assumptions that make OPE effective. Moreover, which offline policy selection using Fitted Q evaluation (FQE) and the Bellman error sample efficient. We conclude with an empirical study comparing FQE and Bellman errors for offline policy selection.
by the sample complexity of OPE. These results imply not
theoretically study the conditions under
INTRODUCTION
Learning policy from offline datasets, known as offline reinforcement learning (RI.), has gained in popularity due to its practicality. Offline RL is useful for many real-world applications, as learning from online interaction may be expensive or dangerous (Levine et al., 2020). For example, training stock-trading RL agent online may incur large losses before learning to perform well, and training self-driving cars in the real world may be too dangerous. Ideally we want to learn a good policy offline, before deployment.
In practice, offline RL algorithms often have hyperparameters which require careful tuning, and whether or we can select effective hyperparameters is perhaps the most important consideration when comparing algorithms (Wu et al., 2019; Kumar et al., 2022). Additionally, performance can differ between algorithms, algorithm selection is also important (Kumar et al., 2022). When specific algorithm is run with a specific hyperparameter configuration, it outputs a learned policy and/or value function. Thus, each sygorihhn-hyperprrameee
configuration produces candidate policy from which we create set of candidate policies. The problem of finding the best- persforerormng policy from a set of candidate policies is called policy selection. While policy selection is typically used for arbitrarily generated.
selection, it is more general since each candidate policy can be
The typical way of finding the best-performing policy in RL is to perform several rollouts for each candidate policy in the environment, compute the average return for each policy, and then select the policy that produced the highest average return. This approach is often used in many industrial problems where A/B testing available. However, this approach assumes that these rollouts can be performed, which necessarily requires access to the environment simulator, luxury not available the offline setting. As such, in offline RL, Monte Carlo rollouts cannot be performed to select candidate policies, and mechanisms select policies with offline data needed.

---

Under review as a conference paper at ICLR 2023
A common approach to policy selection in the offline setting, known offline policy selection, is to perform off off-cy policy evaluation (OPE) to estimate the value of candidate policies from a fixed dataset and then select the policy with the highest estimated value. Typical OPE algorithms include direct methods such as fitted Q evaluation (FQE) estimator (Le et al., 2019), importance sampling (IS) estimator (Sutton & Barto, 2018), doubly robust estimator (Jiang & Li, 2016), model-based estimator (Mannor et al., 2007), and marginalized importance sampling estimator (Xie et al., 2019). Empirically, Tang & Wiens (2021); Paine al. (2020) provide experimental results on offline policy selection using OPE. Similarly, Doroudi et al. (2017); Yang et al. (2022) use OPE estimators for policy selection.
Offline policy selection has been mainly associated with OPE, since these two problem are closely related. is known that OPE is hard problem that requires an exponential number of samples to evaluate any given policy in the worst case (Wang et al., 2020), so OPE can be unreliable for policy selection. As result, follow-up question is: do the hardness results from OPE also hold for offline policy selection? If the answer is yes, then we would need to consider additional assumptions to enable sample efficient offline policy selection.
Moreover, offline policy selection should be easier than OPE intuitively, since estimating each policy accurately might not be necessary for policy selection. There mixed evidence that alternatives to OPE might be effective. Tang & Wiens (2021) show empirically that using TD errors perform poorly because they provide overestimates; they conclude OPE is necessary. On the other hand, Zhang & Jiang (2021) perform policy selection without OPE, by selecting the value function that is closest to the optimal value function. However, their method relies on having the optimal value function in the set of candidate value functions. It remains an open question about when, or even if, alternative approaches can outperform OPE for offline policy selection.
Unfortunately, there is little understanding about the offline policy selection problem to answer the aforementioned questions. Therefore. to provide better understanding, we aim to investigate the question: When can we perform offline policy selection efficiently (with a polynomial sample complexity) for RL? To this end, our contributions are as follows:
We show that the sample complexity of the offline policy selection problem is lower-bounded by the samples need to perform OPF. This implies no policy selection approach can be more sample efficient than OPE in the worst case. On the other hand, OPE can be used for offline policy selection, so the sample complexity of policy selection is upper-bounded by the samples required for OPE. In particular, we show that a selection algorithm that simply chooses the policy with the highest IS estimate achieves nearly minimax optimal sample complexity, which is exponential the horizon.
To circumvent exponential sample complexity, we need to make additional assumptions. We iden- tify when FQE, a commonly used OPE method, is efficient for offline policy selection. Specifically we discuss that FQE is efficient for policy selection when the candidate policies are well covered by the offline dataset. This theoretical result supports several empirical findings.
We explore the use of Bellman errors for policy selection and provide a theoretical argument and experimental evidence for the improved sample efficiency of using Bellman errors compared to FQE, under stronger assumptions such as deterministic dynamics and good data coverage.
2 BACKGROUND
In reinforcement learning (RL), the angentennvionment interaction can be formalized as finite hori- zon finite Markov decision process (MDP) M (S. A. H, v. Q). S is a set of states with size S = [S), and A is set of actions with size A = AA, H E 2+ is the horizon, and E A(S) is the initial state distribution where ASS) is the set of probability distributions over S. Without loss of generality, sampled from Q, that is, S') ~ Q[- a). We assume the reward is bounded in [0, T'eo]] almost surely the total return of each episode is bounded in [0, Vmaz almost surely. The stochastie kernel Q induces a transition probability P S x A + ASS), and a mean reward function r(s, a) which gives the mean reward when taking action in state s.
assume that there is only one initial state sp- The reward R and next state S' are
-1 where म. : A non-stationary policy is a sequence of memoryless policies (F,.
A (A). We assume that the set of states reachable time step h. Sr. S, are disjoint, without loss
2

---

Under review as a conference paper at ICLR 2023
of generality, because we can always define new state space S' = Sx 10, ...,, H --11, it is sufficient to consider stationary policies π : S + A(A).
1}. Then,
Given policy म, for any h [H], and (s,a) E S x A, we define the value function and the action- value function as of (s) := E Σ - r(St, AS, =s] and q% (s. a) : E E r(S,, A,) = AA = respectively. The expectation is with respect to P", which is the probability measure on the random element (So: Ao: Ro.... RØ-1 induced by the policy x. The optimal value function is defined by (s) sup, x "I (s), and the Bellman operator is defined by
(T (s, a) = r(s, a) + Σ s'ES
P(s, a, s')
max d'EA
The Bellman evaluation operator is defined by
(T (T)))(ssa)) = =(ss + Σ P(s,a,'') Σ
T(d'ls')qn (s',s'''a))
e'ES
d'EA
We use (xx to denote the value of the policy n, that is, the expected return from the initial state [Tx) = v" (so). A policy ı is optimal if ((T)) v² (x0)).
In the offline RL setting, we are given a fixed set of transitions with samples drawn from a data distribution μ.. In this paper, we consider the setting where the data is collected by a behavior policy Tr since the data collection scheme is more practical (Xiao et al., 2022) and is used to collect data for benchmark datasets (Fu et al., 2020). We use di, to denote the data distribution
the horizon
h by following the policy æ,, that is, di (s, a) = (S, = s, An = a), and (s, a) := PT (SA. =
8, A, a).
Notation. We use [H] to denote the set [H] = (0, 1,..,.. H - 1}. Given a value function q and a state-action distribution Ju, the norm is defined as [1911 = E,,a u(s // and the
max norm is defined as ||q]loo == max,aa (q(s, a))s
3 SAMPLE COMPLEXITY OF OFFLINE POLICY SELECTION
We consider the offline policy selection (OPS) problem and offline policy evaluation (OPB) prob- lem. We follow a similar notation and formulation used in Xiao et al. (2022) to formally describe these problem settings. The OPS problem for fixed number of episodes (S, A. H, v. n, I). I is set of instances of the form (M, da, II) where M E MMSS, A, H. v) speci- fies an MDP, de is distribution over a trajectory (So, Ag, Ro...., .o....,,R. RH-1) by running the behavior policy mi on M, and II is finite set of candidate policies. We consider the setting where II has small size and does not depend on S, A or H.
given by the tuple
An OPS algorithm takes input batch of data D, which contains n trajectories, and a set of candidate policies II, and outputs a policy π E II. We say an OPS algorithm is (E, -'soun on instance (M, do, 11) if
Pro (Jar(E(D,, IT) 2 JM((T)) - 2)
where n is the best policy in TI. We say an OPS algorithm L is (e, ().8)-oound on the problem (S, A, H, v, n, I) if it is sound on any instance (M, do. 11) E I.
Given a pair (s, (s, the sample complexity of OPS is the smallest integer such that there exists a behavior policy Th and an OPS algorithm such that L is (c, -sound on the OPS problem (S, A, H, 24 n. I(Ta) where I(Tx) denotes the set of instances with data distribution d,. That is, if the statistical complexity is lower-bounded bounded by n, then, for any behavior policy Tb, there exists an MDP M and set of candidate policies II such that any (c, 5)sunn OPS algorithm on (M, dr, II) requires at least n samples.
Similarly, the OPE problem for fixed number of episodes n is given by (8,A, H, I). I is set of instances of the form (M, do, т) where M and d, are defined as above, and π is target policy. An OPE algorithm takes as input batch of data D and a target policy n, and outputs an estimate of the policy value. We say an OPE algorithm L is (s, -)-uun on instance (M, db. TT) if
Pro (L( π) JJr(m) & <&) 2)>1 1-
We say an OPE algorithm is (e. sound on the problem (S, instance (M, do, π) I. Note that should be less than Vmaan/2 otherwise the bound is trivial.
A, H, v. n, I) if it is sound on any
3

---

Under review as a conference paper at ICLR 2023
3.1 OPE ALGORITHM AS SUBROUTINE FOR OFFLINE POLICY SELECTION
It is obvious that a sound OPE algorithm can be used for OPS, so the sample complexity of OPS is upper-bounded by the sample complexity of OPE up logarithmic factor. We state this formally in the theorem below. The proof can be found in Appendix A.I.
Theorem 1. (Upper bound on sample complexity of OPS) Given MDP M, a data distribu- tion de. and a set of policies II, suppose that, for any pair (e, 8), there exists an (e, d)-sound OPE algorithm L on any OPE instance I {(M, do, ONoPE S, A, H, e, 1/8)). Then there exists an (e, 8)-nound OPS algorithm for the OPS problem instance (M, do. I1) which requires at most (NNOPE (,, A, H.E, E, [1] episodes.
т E II] with sample size at most
In terms of the sample complexity, we have an extra Vlog (11)// term for OPS due to the union bound. For hyperparameter selection in practice, the size of the candidate set is often much smaller than n, so this extra term is negligible. However, if the set is too large, complexity regularization (Bartlett et al., 2002) may need to be considered.
3.2 OFFLINE POLICY SELECTION IS NOT EASIER THAN OPE
We have shown that OPS is sample efficient when OPE is sample efficient. However, it remains unclear whether OPS can be sample efficient when OPE is not. In the following theorem, we lower bound the sample complexity of OPS by the sample complexity of OPE. As a result, both OPS and OPE suffer from the same hardness result, and we cannot expect OPS to be sample efficient under conditions where OPE is not sample efficient.
Theorem 2 (Lower bound on sample complexity of OPS). Suppose for any data distribution de and any pair (s, 8) with & E (0, Vmaa/22 and d E (0, 1). there exists an MDP M and a policy x such -ound OPE algorithm requires at least ((NoPE A, H, c, episodes. Then there exists an MDP M' with S' = S + 2, H' = + 1, and a set of candidate policies such that for any pair (e, 5) with & E (0, V.naa/ /3) and E 1/m) where == [log(V /e)] 2 any (e, 8) 8--oound OPS algorithm also requires at least (NNOE(S, A, H, s, 1/ (m(m)))) episodes.
that any (c.und
The proof sketch is to construct an OPE algorithm that queries OPS subroutine. As result, the sample complexity of OPS is lower bounded by the sample complexity of OPE. We use the reduction first mentioned in Wang al. (2020), and present proof in Appendix A.2.
There exist several hardness results for OPE in tabular settings and with linear function approxi- mation (Yin & Wang, 2021; Wang al., 2020). Theorem implies that the same hardness results hold for OPS. We should not expect to have a sound OPS algorithm without additional assumptions. Theorem 2. however, does not imply that OPS and OPE are always equally hard. There are instances where OPS is easy but OPE is not. For example, when all policies in the candidate set all have the same value, any random policy selection is sound. However, OPE can still be difficult in such cases.
3.3 IMPORTANCE SAMPLING ACIIEVES NEARLY MINIMAX OPTIMAL SAMPLE COMPLEXITY
We present an exponential lower bound on the sample complexity of OPE in Theorem 5 in the appendix, which uses the same construction from Xiao et al. (2022). By the lower bound on the sample complexity of OPE and Theorem 2, we now have lower bound for OPS.
Corollary (Exponential lower bound on the sample complexity of OPS). For any positive integers S, S,A, H with S > 2H and a pair (s, 6) with < S v1/8. 8 (0. 1), any (s, (E,6)-soum) OPS algorithm needs at least 4(A /c²) episodes.
We can use a common OPE method, importance sampling (IS), with random behavior policy for policy selection. Recall the IS estimator (Rubinstein, 1981) is given by
H
H-1 1
j(m) =
Th
W;
G
where n is the number of episodes in the dataset D. We now provide an upper bound on the sample complexity of OPS using IS. The proof can be found in Appendix A.3.
4

---

Under review as a conference paper at ICLR 2023
Theorem 3 (OPS using importance sampling). Suppose the data collection policy is uniformly random, that is, T)(als) = I/A for all (s, a) E x A, and |G,] I Vmax almost surely. Then the selection algorithm L that selects the policy with the highest IS estimate is (e, 6)-sundddd with O(A Vaar In (TT16)/)3) episodes.
The theorem suggests that IS achieves nearly minimax optimal sample complexity for OPS to a factor and logarithmic factors. There are other improved variants of IS, including per-decision IS and weighted IS (Precup et al., 2000; Sutton & Barto, 2018). However, none of these variants can help reduce sample complexity in the worst case because the lower bound Corollary holds for any OPS algorithm. The result suggests that we need to consider additional assumptions on the environment, the data distribution, or the candidate set to obtain guarantees for OPS.
Note that Wang et al. (2017) have shown that IS estimator achievew the minimax mean squared error for the OPE problem. Our result shows that IS also achieves a (nearly) minimax sample complexity for the OPS problem.
There are other examples where OPS efficient by using particular OPE methods. For example, Liu et al. (2021) consider environments where the state contains exogenous variables; the agent has limited impact on those exogenous variables; and the agent has the knowledge about the endoge- dynamic. In such environments, they provide sound OPE method to select hyperparameters. Another example is when an accurate simulator of the environment is available. The simulation lemma (Kearns& & Singh, 2002) shows that can evaluate any policy accurately and thus perform sound OPS. All these specialized strategies indicate that we can perform OPS efficiently, under much stronger assumptions.
CONDITIONS FOR SAMPLE EFFICIENT OFFLINE POLICY SELECTION
In the following sections, we discuss the conditions under which OPS using Fitted Q-iteration and Bellman Error are efficient for offline policy selection. These results are based on existing theoretical analysis of FQE and BE, for example, Chen & Jiang (2019); Le et al. (2019); Xie al. (2021); Duan et al. (2021).
4.1 OFFLINE POLICY SELECTION USING FITTED Q-EVALUATION
Fitted Q-evaluation (FQE) is a commonly-used OPE method that has been shown to be effective for policy selection in benchmark datasets (Paine et al., 2020). FQE applies the empirical Bellman evaluation operator on the value estimate iteratively: given a function class F, we initialize 9H-1 arg fer In (f. gh.1)) where
0, and, for h H 2,...,,. O. qn
(L.s. = Da
(f(s,a) (s.O.Ts)))D
Σ
1 (s'
and D2 is the dataset at horizon with distribution ph. The FQE estimate for J(T) is J(T) Ex-x(11s)) [qu(su. a)).
Intuitively, we should be able to evaluate the value of all policies covered by the data distribution. If the candidate policy set is a subset of the set of policies covered by data, then we can do policy selection well. To define the notion of well-covered policies, we use the measure of distribution shift introduced in Xie et al. (2021). Given a non-negative real value C, we define IT(C, p, be the set of policies covered by the data distribution μ, that is, for any policy æ Iu, I|/-T" s'llag T f-T= < C holds for any h E [H].
max
The theorem below provides a theoretical guarantee for OPS using FQE, The proof can be found in Appendix A.4.
Theorem 4 (Offline policy selection for well-covered policies). Suppose have function class F with Rademacher complexity (F). an approximation error Eapz. and an optimization error Eopt (see Appendix A.4 for the definitions). If there exists non-negative value C such that II C
5

---

J(r;) Under review as a conference paper at ICLR 2023
pt, then the OPS algorithm L that selects the policy with the highest FQE estimate satisfies
Pr ((C(D, 2 J(=)) - 2H 2HvC VCV Copt + Eapa + co H (. + co H2 log (1TT/
2 1
for some constant Co.
If we have a good function class and an optimizer, then FQE only requires a polynomial number of episodes for OPS under the assumption that all candidate policies are well-covered by the data. However, in practice, we need to choose the function class and optimization hyperparameters. It is easy to choose optimization hyperparameters such the learning rate. We can do so by choosing the optimizer with the lowest Copt- This can be done by selecting the optimization hyperparameters that
result in the smallest TD errors En In (gh: gh+1) on validation dataset. However, selecting func- tion class is nontrivial, because we need to balance the approximation error, the complexity measure and how well the data covers the candidate policies. In our experiments, we fix the function class as a neural network model with the same architecture and tune the optimization hyperparameters.
Theorem presents positive result that OPS can be sample efficient when selecting amongst well- covered policies. However, if one of the candidate policies is not well-covered, then the FQE esti- mate may overestimate the value of the uncovered policy and resulting poor OPS. is known that FQE can even diverge (Sutton & Barto, 2018), due to the fact that it combines off-policy learning with bootstrapping and function approximation, known as the deadly triad. One way to circumvent the issue of uncovered policies is find way to assign low values for uncovered policies. One heuristic way is to early stop when FQE diverges and assign lower value estimates to policies for which FQE diverges since the policy is likely to be not covered by the data. Another heuristic is to use a pessimistic version of FQE that penalizes policies whose data distribution dissimilar from the behavior distribution. This approach is similar to CQL, but it introduces an additional hyperpa- rameter to control the level of pessimism, which again is not easy to tune in the offline setting.
Practical insight. Our result explains the empirical findings in Paine et al. (2020) that FQE is suf- ficient for selecting hyperparameters for conservative algorithms and imitation learning algorithms. A recent paper (Kumar et al., 2022) discusses when we should use pessimistic offline RL behav- ioral cloning under specific conditions. Our result shows that we can in fact run both algorithms and choose the one with highest FQE estimate. With high probability, we can choose the best policy among offline RL and behavioral cloning algorithms without considering specific conditions.
4.2 OFFLINE POLICY SELECTION USING THE BELLMAN ERROR
In this section, we investigate whether OPS using the estimated Bellman error has any advantage over FQE. Most value-based methods output value functions and we often perform policy selection over value functions by considering the greedy policies with respect to these value functions. Sup- pose we are given candidate set of value functions {q K 1. natural criterion is to select the value function that is closest to the optimal value function, that is. 1/4: q" ol is the smallest. A justifi- cation of choosing the smallest ||q: q" ol is that the value error gives us lower bound where is the greedy policy with respect to qs. That is, ((T)) 2 J(TT) )- 2/ [q: - q" lloo (Singh & Yee, 1994). Therefore, choosing the smallest |q: --1'l equivalent to choosing the largest lower bound on the policy value. While we do not know q², it might still be possible to derive a similar lower bound on the policy value, possibly by estimating the Bellman error (BE).
A potential use case of the BE is that if the data distribution covers the entire state-action space well, then the BE is a good surrogate for the policy value. More formally, the concentration coef- d[(s.a)
ficient C' is defined as the smallest value such that max..a. pals.a) < C' for all policies π. By the performance difference lemma (Kakade, 2003), we can show that
H-1
J(m) 2 [(TT - CH
Σ 11qa - TTu41ll2,pp h=
That is, the Bellman error evaluated on the dataset can be a useful indicator of the quality of the greedy policy, if C' is small. Note that a small concentration coefficient is a stronger assumption
compared to the assumption of FQE. To be more specific, the condition maX. (4 (3.00.
(s.a) C for

---

Under review as a conference paper at ICLR 2023
all policies E II implies max T C for all policies E I1. That is, we only need coverage for all policies in the candidate set for sample efficient OPS with FQE. However, for BE, the measure of distribution shift needs to be bounded for all policies.
Finding the value function with the lowest Bellman error in deterministic environments is sample efficient. To see why this is the case, let k be the output index of the selection algorithm that selects the index of the value function with the smallest empirical Bellman error, then with probability at least 1 5, for some constant co.
log (1T) 72
1 Tqx 12,0 S min llq: -Tqill,, + co V 1.11.111
-T 2. for simplicity. Therefore, the sample size n only needs scale with V22 maa- In contrast, the sample size of FQE depends on the complexity of the function class ((( (F)). If we use a function class with high complexity to perform FQE, then expect
where we denote 1lg:- -Tx TT
that BE is more sample efficient method for selection compared to FQE when the data covers the state-action space well, that is, when C is small.
If the concentration coefficient is large infinite, then the Bellman error can be poor indicator of the greedy policy's s performance. For example, Fujimoto et al. (2022) provide several examples where BE is poor surrogate for value error even when the environment is deterministic. Moreover, several empirical works have shown that OPS using the Bellman error or value estimate from of- fline RL algorithms underperform using OPE estimates (Tang & Wiens, 2021). Our result provides theoretical reasoning for these experimental observations. Since, in most practical scenarios the concentration coefficient can be very large or infinite, OPS using the BE can be poor.
Estimating Bellman error in stochastic environments. Estimating Bellman error in stochastic environments potentially requires more samples. This is because doing so often involves fitting a function (Antos al., 2008: Farahmand & Szepesvári, 2011), and resultingly the sample complexity of estimating the BE accurately depends on the complexity of the function class. We hypothesize that it makes the sample complexity similar to FQE. If the sample complexity is similar to FQE and policy selection using BE requires stronger assumptions, then it is natural to use FQE in stochastic environments even if the data coverage is good. We leave the exact analysis of the sample complexity of OPS using estimated Bellman Error in stochastic environments for future work.
5 EMPIRICAL COMPARISON BETWEEN FQE AND BE
In this section, we aim to validate our results experimentally by answering the following questions: (1) How do FQE and BE perform when (a) all candidate policies are well-covered, (b) the data contains diverse trajectories or (c) the data neither covers all candidate policies nor provides diverse trajectories? (2) Can BE be more sample efficient than FQE for OPS?
We conduct experiments on two standard RL environments: Acrobot and Cartpole. We first generate of candidate policy-value pairs (T, 91 k by running CQL (Kumar et al., 2020) with different hyperparameters on a batch of data collected by an optimal policy with random actions taken 40% of the time. We then use either FQE or BE rank the candidate policies, and select the top-k policies. The OPS problem we described in this paper is a special case with A = 1. We also included a random selection baseline where the randomly choose k policies from the candidate set. To evaluate the performance of top-k policy selection, we consider the top-k regret which is used in the existing literature (Zhang & Jiang, 2021; Paine et al., 2020). Top-k regret is the gap between the best policy within the top-k policies, and the best among all candidate policies. More experimental details can be found in Appendix B.
In the first set of experiments, we generate three different datasets: (a) well-covered data is generated such that all candidate policies are well-covered, (b) diverse data includes more diverse trajectories to obtain a lower concentration coefficient, and (c) expert data is collected by deterministic and optimal policy. Figure| shows the top-k regret with 900 episodes of data. FQE performs very well with small regret well-covered and diverse data. BE does not perform well with well- covered data. However, with diverse data, BE performs much better. Surprisingly, for expert data, BE performs better than FQE even though the data distribution has an extremely large concentration
7

---

Under review as a conference paper at ICLR 2023
Acrobot Diverse Data
Well-covered Data
Expert Data
30
30
40
Regret
20
20
30
BE
FQE
10
10
20
random
10
0
1
5
10
1
5
10
10
k
k
Cartpole Diverse Data
Well-covered Data
Expert Data
Regret
150
100
100
BE
100
FQE
50
50
50
random
0
0
5 k
10
10
10
k
Figure 1: Top-k regret with varying k and 900 episodes on Acrobot and Cartpole. The results averaged over 5 runs with one standard error.
Acrobot
Top-1 regret
Top-5 regret
Top-10 regret
40
40
Regret
30
30
20
BE
20
20
FQE
10
10
10
random
0
0
0
10
104
103
10
102
103
10
102
10
Cartpole
Top-1 regret
Top-5 regret
Top-10 regret
30
10
Regret
100
BE
20
FQE
50
10
random
901
901
0
102 10
10
103
10a
102
10a
n
n
Figure 2: Top-k regret with varying sample size on Acrobot and Cartpole with diverse data.
coefficient. Acrobot, BE tends perform better with larger i even with good data coverage, while FQE can have small t regret as long as the data covers the candidate policy.
In the second of experiments, we use diverse data. Figure 2 shows the results with varying numbers of episodes for top-k regret with & E {1, 10). BE performs better than FQE when the sample size small (less than 100 episodes) most cases. The random selection baseline expected to perform independent of the data used for OPS. We expect to larger gap when the environment has a high-dimensional state spacee so a function class with large complexity is needed for FQE.
In summary, these experimental results validate our theoretical results. We show (1) FQE performs very well when the candidate policies well-covered; (2) BE performs well under diverse data coverage assumption; and (3) neither perform well without their corresponding data coverage con- ditions. Moreover, BE can be sample efficient than FQE under good data coverage.
8

---

Under review as a conference paper at ICLR 2023
6 RELATED WORK
In this section we provide
comprehensive survey of prior work model selection for inforcement learning. In the online setting, model selection has been studied extensively across contextual bandits (Foster al., 2019) reinforcement learning (Lee al., 2021). In the online setting, the goal is to select model classes while balancing exploration and exploitation to achieve low regret, which is very different from the offline setting where no exploration performed.
In the offline setting, besides using OPE for model selection, Farahmand & Szepesvári (2011) and Zhang & Jiang (2021) consider selecting a value function that has the smallest Bellman error or is the closest to the optimal value function. Farahmand & Szepesvári (201) I) consider selecting a value stochastic environments such that with high probability, l/g: T q 1 I min; l/g. T Tqi 11.112,,p + where k is the output of selection algorithm. To estimate the Bellman error, they propose to fit a regression model qi to predict q; and bound the Bellman error by 11% ب112, + b, where b; is an upper bound the estimation error of the regression. However, as we show in this paper, even in a deterministic environment where selecting the smallest Bellman error is easy, it does not imply effective OPS unless the data coverage is good.
function among a set of candidate value functions
Zhang& & Jiang (2021) consider the projected Bellman error with a piecewise constant function class. They show that if q² is in the candidate set and stronger data assumption is satisfied, then they can choose the optimal value function by selecting the value function with the smallest Batch Value-Function Tournament loss (BVFT). Xie & Jiang (2021) consider BVFT with approximation error. In practice, their method is computationally expensive since it scales with ((III(²) instead of O making the method impractical when the candidate set not small.
Other work on model selection in RL is in other settings: selecting models and selecting amongst OPE estimators. Hallak et al. (2013) consider model selection for model-based RL algorithms with batch data. They focus on selecting the most suitable model that generates the observed data, based on the maximum likelihood framework. Su et (2020) consider estimator selection for OPE when the estimators can be ordered with monotonically increasing biases and decreasing confidence inter- vals. They also show that their method achieves an oracle inequality for estimator selection.
To the best of our knowledge, there is no previous work on understanding the fundamental limits for the OPS problem in RI. There one related work in the batch contextual bandit setting, studying the selection of linear model (Lee et al., 2022). They provide hardness result suggesting it is impossible to achieve an oracle incquality that balances the approximation error, the complexity of the function class, and data coverage. However, their results restricted only to the contextual bandit setting. In this paper, we consider the more general problem, selecting a policy from a set of policies, in the RL setting.
7 CONCLUSION & DISCUSSION
In this paper, we have made progress towards understanding when OPS is feasible for RL. Our main result that the sample complexity of OPS is lower-bounded by the sample complexity of OPE, is perhaps expected. However, our knowledge, this has never been formally shown. This result implies that without conditions to make OPE feasible, we cannot do policy selection efficiently. We provided theoretical statements with experimental evidence demonstrating that FQE is sample efficient when all candidate policies are well-covered and that BE can be more sample efficient under stronger data coverage.
A natural next step from this work is to consider the structure or properties of the candidate policy set. For example, Kumar et al. (2021) use the trend in the TD error to select the number of training steps for CQL. The early stopping criterion could be selected based on errors on the dataset, and is possible that such an approach could be proved to be sound in certain settings. As another example, if we know that performance is smooth in a hyperparameter for algorithm, such regularization parameter, then it might be feasible to exploit curve fitting to get better estimates of performance. Our work does not yet answer these questions, but it does provide some insights into OPS that could lead to the development of sound hyperparameter selection procedures for roal-world RI. applications.

---

Under review as a conference paper at ICLR 2023
REFERENCES
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 2008.
Peter I. Bartlett, Stéphane Boucheron, and Gábor Lugosi. Model selection and error estimation. Machine Learning. 2002.
Jinglin Chen and Nan Jiang. Information- considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019.
Shayan Doroudi, Philip S Thomas, and Emma Brunskill. Importance sampling for fair policy selec- tion. Grantee Submission, 2017.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. International Conference on Machine Learning, 2021.
Amir-massoud Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Ma- chine Learning, 2011.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
Scott Fujimoto, David Meger, Doina Precup, Ofir Nachum, and Shixiang Shane Gu. Why should i trust you, bellman? the bellman error is poor replacement for value error. arXiv preprint arXiv:2201. 12417, 2022.
Assaf Hallak, Dotan Di-Castro, and Shie Mannor. Model selection in markovian processes. In International Conference on Knowledge Discovery and Data Mining, 2013.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, 2016.
Sham Machandranath Kakade. On the sample complexity reinforcement learning. University of London, University College London, 2003.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine Learning, 2002.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 2020.
Aviral Kumar, Anikait Singh, Stephen Tian, Chelsea Finn, and Sergey Levine. A workflow for offline model-free robotic reinforcement learning. arXiv preprint arXiv:2109.108 2021.
Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. When should we prefer offline rein- forcement learning over behavioral cloning? arXiv preprint arXiv:2204.05611, 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Inter-
national Conference on Machine Learning, 2019.
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In International Con- ference on Artificial Intelligence and Statistics, 2021.
Jonathan Lee, George Tucker, Ofir Nachum, and Bo Dai. Model selection in batch policy optimiza- tion. In International Conference on Machine Learning, 2022.
10

---

Under review as a conference paper at ICLR 2023
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto-
rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
Vincent Liu, James R Wright, and Martha White. Exploiting action impact regularity and exogenous state variables for offline reinforcement learning. arXiv preprint arXiv:2111.08006 2021.
Shie Mannor, Dunean Simester, Peng Sun, and John N Tsitsiklis. Bias and variance approximation in value function estimates. Management Science, 2007.
Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. Hyperparameter selection for offline reinforeement learning. arXiv preprint arXiv:2007.09055 2020.
Doina Precup, Richard S Sutton, and Satinder Singh. Eligibility traces for off-policy policy eval- uation. In International Conference on Machine Learning, 2000.
Reuven Y Rubinstein. Simulation and the Monte Carlo method. John Wiley & Sons, 1981.
Satinder P Singh and Richard C Yee. An upper bound on the loss from approximate optimal-value functions. Machine Learning, 1994.
Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. Adaptive estimator selection for off-policy evaluation. In International Conference Machine Learning, 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 con- siderations for healthcare settings. In Machine Learning for Healthcare Conference, 2021.
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. 1100000.1119990 1895, 2020.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference on Machine Learning. 2017.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: 191 1361, 2019.
Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. The curse of passive data collection batch reinforcement learning. In International Conference on Artificial Intelligence and Statistics, 2022.
Tengyang Xie and Nan Jiang, Batch value-function approximation with only realizability. In Inter- national Conference on Machine Learning, 2021.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. Advances Neural Information Processing Systems, 2019.
Tengyang Xie. Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. pessimism for offline reinforcement learning. Advances in Neural Information Processing Sys- fems, 2021.
Mengjiao Yang. Bo Dai, Ofir Nachum, George Tucker, and Dale Schuurmans. Offline policy se- lection under uncertainty. In International Conference on Artificial Intelligence and Statistics, 2022.
Ming Yin and Yu-Xiang Wang. Optimal uniform ope and model-based offline reinforcement learn- ing in time-homogeneous, reward-free and task-agnostic settings. Advances in Neural Information Processing Systems, 2021.
Siyuan Zhang and Nan Jiang. Towards hyperparameter-free policy selection for offline reinforce- ment learning. Advances in Neural Information Processing Systems, 2021.
11

---

Under review as a conference paper at ICLR 2023
A TECHNICAL DETAILS
A.1 PROOF OF THEOREM 1
Theorem (Upper bound on sample complexity of OPS) Given an MDP M, a data distribu- tion do, and set of policies II, suppose that, for any pair (e, 8), there exists an (e, d)-sound OPE algorithm on any OPE instance I E {(M, ds, т) : T E II} with a sample size at most O(NOPg S, A, H, E, 1/8)). Then there exists an (e, souud OPS algorithm for the OPS problem instance (M, dg III which requires at most ((NOPE A, H.E, [I] episodes.
Proof. The OPS algorithm L(D, II) for a given (c, 5) works as follows: we query an ('', )')-su OPE algorithm for each policy in Il and select the policy with the highest estimated value. That is, C(D, II) outputs the policy गे == argmax (TT), where J (TT) is the value estimate for policy by the
(e', -sound OPE algorithm with data D.
By definition of an ('',8")-souni -sound OPE algorithm we have
Pro (15(T) (()) 21-)) II.
Applying the union bound, we have
Pro-a, (VT E nT, J(+) (() 5'
(1)
Let r! denote the best policy in the candidate set 11, that is, xl argmax J(T). With probability xell
1 - 6'|[I|, we have
2 ((R) -
- J( (()))) 2
The first and third inequalities follow from equation and the second inequality follows from the definition of s.
Finally, by setting = 8/| and 5 = =8/2, we get
Pro-d, (J(#) 2 J(TT)( - 1 1-
That is, L is an (souud OPS algorithm. This requires at most O(NOPE A,H, (1/))) samples.
A.2 PROOF OF THROREM 2
Theorem (Lower bound sample complexity of OPS). Suppose for any data distribution de and
any pair (c, 5) with E E (0, Vinar/2) and 5 E (0, 1), there exists an MDP M and a policy æ such that any (e, sound OPE algorithm requires
least 2(NOPE(S, A, 11, e, 1/6)) episodes. Then there exists an MDP M' with S" = S + 2, H' = Hl - 1, and a set of candidate policies such that for any pair (e. 8) with e E (0, Vmnaa/3) and (0, 1/m) where m = [oog(Vaaw/ 2 any (e, 8o-ud OPS algorithm also requires at least ((NoPE A, H. 1/(m)))) episodes.
Proof. Our goal is to construct an (c, 5)-sound OPE algorithm with 5 E (0. and E I0, Vmax /2] To evaluate any policy π with dataset D sampled from do we first construct a new MDP M, with two additional states: an initial state and terminal state 81. Taking 81 with reward r. Taking 0g at So transitions to the initial state in the original MDP M.
80 transitions to
Let II { } } be the candidate set in M, where (5o) 01 and T2(5)) a2 and T2 (als) T (a)ss) for all (s,a) a) E S x A. Since T always transitions to 81, never transitions to states in MDP M. Therefore, Wi
be arbitrary for all (s, a) E S A. We can add any number of transitions (Su, s) and (So, 02 0, s) in D to construct the dataset D, with distribution de,r arbitrarily.
Suppose we have (e', 8') -ounnd OPS algorithm, where set e' 2z/3, 8' = 8 5/m and [log( V Tm)). Note that if this assumption does not hold, then it directly implies that the sample complexity of OPS is larger than ((NorE(S, A, 1/5)). Our strategy will be to iteratively set
12

---

Under review as a conference paper at ICLR 2023
the reward of MDP M, and run our sound OPS algorithm II and using bisection search to estimate a precise interval for (T).
The process is follows. By construction, our OPS algorithm will output either TT, which has value M. (T)) = r, or output T2, which has value JM, (T2) = JM (T). That is, has the same value as in the original MDP. Let consider the following cases. Let tt be the best policy in IT for MDP M,.
Case I: the OPS algorithm selects mi- We know, by definition of sound OPS algorithm, that Pr(JM, (TT) 2 Jas, ( E') 2 8'
Pr(r 2 max JM, (T2) - e') 8' Pr(Jar, (T2) S + 8
Case 2: the OPS algorithm selects T2.
Pr(Jar, (72) 2 JM, (T1) - 2 1-
Pr(Juu, (T2) 2 max (r, JM, (T2)) ) = 2 2--8
Pr(Jas,TT) 2 r r - 5') 2-
Given this information, we describe the iterative process by which we produce the estimate J(r), We first U V Vmaz = 0 and D+ and run the sound OPS algorithm with input D,- of sample size and the candidate set II. Then if the selected policy is Tι, then we conclude the desired event ((x) I r + e' occurs with probability at least 8', and set U equal to r. If the selected policy is 22, then we know the desired event J(T) 2 5 occurs with probability at least 1 8', and set L. equal to r. We can continue the bisection search until the accuracy is less than e', that is, U ---L L S s', and the output value estimate ((x) 2
E+L
If all desired events at each call occur, then we conclude that L - e' S J(T) S U + + and thus (J(m) - |(x) c. The total number of OPS calls is most Setting 8' 5/m and applying union bound, we can conclude that with probability least 6, [T() J [(x) S..
Finally, since any (e, ().ouu OPE algorithm on the instance (M) needs at least ((Nore(S, A, H, 1/8)) samples, the (e', ('sound OPS algorithm needs at least ((NoPE(S, A, 1/8)), or ((NoPE(S, A, H. 3z/2, 1/mm"))m))))) samples for at least one of the in- stances (M,, do.r. II).
A.3 PROOF OF THEOREM 3
Theorem 3 (OPS using importance sampling). Suppose the data collection policy is uniformly random, that is, (als)) = 1/A for all (s, a) E x A, and [G,| < Vmaa almost surely. Then the selection algorithm L that selects the policy with the highest IS estimate is (s, 0)-sound with OAA ((A"Vaaa Vmar In (()) episodes.
Proof. Since the policy is uniform random, we know [WG.,| < A max almost surely. Moreover, the importance sampling estimator is unbiased, that is, E[W.G.] = [(T).. Using the Bernstein's inequality, we can show that the IS estimator satisfies
Pr ((Tx)) - [(x)]] 2A Vmaz In (2/8)
2Vrr(W.G.) In (2/5)
2 1-5
3n
n
for one candidate policy Using the union bound, we have
2A Vmaa In (2(11)/0)
2V(WGG) In (2 /8)
Pr (((Th)- [(TA]] <
Ak
21-8
3m
That is,
4A V maz In (8)1
SV(WGG,) In (2/11/8))
Pr J(C(D.I)) J(T!)
21-6
3n
n
13

---

Under review as a conference paper at ICLR 2023
Figure 3: Lower bound construction.
For the variance term,
V(W,G,) = ? -
S /E & A Vmaz
The second inequality follows from the Cauchy-Schwarz inequality. 32A Vmaz In (2) L is (e, -sounnd.
Therefore, if n >
Theorem 5 (Exponential lower bound on the sample complexity of OPE). For any positive integers S, A, H with S > 2H and a pair (e, 6) with < v1/8. ō (0, 1), any (e, (s,u)- OPE algorithm needs at least (2A4 In (1/8)/e²) episodes.
Proof. We provide proof which uses the construction from Xiao et al. (2022). They provide the result for the offline RL problem with Gaussian rewards. Here we provide the result for OPE problem with Bernoulli rewards since assume rewards are bounded to match Theorem 3.
We can construct an MDP with 5 states, actions and 2HT states in Figure Given any behavior policy wh, let a₁ arg min, (t(a]s)) be the action that leads to the next state 84+1 from state 8h, and all other actions lead to an absorbing state s%.- Once we reach an absorbing state, the agent gets zero reward for all actions for the remainder of the episode. The only nonzero reward is in the last state -H-1. Consider a target policy that chooses ag for state 84. for all h 0,..., H 1, and two MDPs where the only difference between them is the reward distribution sH-1- MDP has Bernoulli distribution with mean 1/2 and MDP has Bernoulli distribution with mean 1/2 25. Let P, denote the probability measure with respect to MDP and P2 denote the probability measure with respect to MDP 2.
Let e denote the OPE estimate by an algorithm L. Define an event (f < -c. Then (e, 8)-oun if
P (E) (E 8.
This is because L is not (c, 8)-uunnd if either (f } - -) 5 or -e) 2 8. Using the Bretagnolle- Huber inequality (See Theorem 14.2 of Lattimore Szepesvári (2020)), we know
(i(E) + F2(
2
2
By the chain rule for KL-divergence and the fact that P1 and Pz only differ in the reward for (H=-1,0H-1) we have
1S H-1 SH-1,A ah-1) ( log 1/2 1/2-5
1/2
1 log
1/2
(2) E,
2
1/2
1 =a=-i) (-1 log (1 - -467)
P. 11 = -
n
AH
The last inequality follows from log (1 - -4 < 2 < 1/2 (Krishnamurthy et al., 2016)
and P. (s(())
4 1 = =0==== 1/A from the construction of the MDPs.
14

---

Under review as a conference paper at ICLR 2023
Finally,
(I + (2(
1
n
exp (-
2
4
A
which is larger than 8 if A ln(1/48)/88 episodes.
As result, we need at least Q(A4 In (1/6)/E2)
A.4 PROOF OF THEOREM 4
Assumption (Approximation error). For any policy E II and h [H] assume the approxi- mation error is bounded by Eapz, that is,
sup inf Ilf - 7 912,,, S gE FEF
Sapz-
Assumption (Optimization error). Given a target value function we want to find the empirical risk minimizer
arg min i(f.g).
JEF
We assume we have an optimization oracel that can return a value function such that the optimiza- tion error bounded, that is,
i(f.)) s <((j,)) + Copt-
Definition (Rademacher complexity). Given function class F, let X {ar,.... .nd denotes n fixed data points at horizon h following the distribution ph. the empirical Rademacher complexity defined as
1
Rx(F) = sup SEF
Σ oxf(( |x
where the expectation is with respect to the Rademacher random variables a; The Rademacher complexity is defined as R (F) = E Rx (F) where the expectation is with respect to the n data points. Finally, to simply the notation, we define (T) m R (F) as the maximum Rademacher complexity over all horizons.
Lemma 1 (Excess risk bound, modification from Theorem 5.2 of Duan al. (2021)). Let (.....----11 be the output of FQE with n sample drawn from the data distribution fau at each horizon h. Then we have, with probability 6, the following holds for all h O,..., H
log (H/8)
1lgh - T 94+112 S Eopt + Eapa + call (F) + col
for some constant co > 0.
Proof. For each horizon h E [H], let 9h be the output value function such that i(gh, qu+1) S i(@n. (h+1) + Sopt where qn is the empirical minimizer, that is, dn. arg minger 4, (f, 41+1). It follows i(gh; fn+1) E(gh 9h+1) + Copt where d) is the population minimizer, that is, g arg min [| - Tqu+1l 112,pa Then follow the proof of Theorem 5.2 in Duan et al. (2021) by
takeing fú. = Th. we have
log (H/8)
l1gn T qh+1 112pp S Eopt + Eapz + cHH + cH2
holds for all = 0,...,
with probability least 1 8.
Theorem 4 (Offline policy selection for well-covered policies). Suppose have function class FF with Rademacher complexity (F), an approximation error Eapz. and an optimization error Eopt (see Appendix A.4 for the definitions). If there exists non-negative value C' such that C IIC, F), then the OPS algorithm L that selects the policy with the highest FQE estimate satisfies
Pr J(C(D, 2 J(xt) 2H 2HVCH VCV Eopt + Capr + c. HoHR + c. H2 (11))
2 1-5
for constant Co.
15

---

Under review as a conference paper at ICLR 2023
Proof. First fix policy E II. Let q (Q0....-HH-1) 9H-1) be the output of FQE with n sample drawn from the data distribution ph at each horizon h, then ll - T qh+ lla I Eopt + Eapz +
(.......
Cp H R (F) + co Ha
HT2 / log (H/4) from Lemma 1 for some constant c0-
" By the definition of II(C,, ue F), we know 11 - mn-llll I Ol T Tngntlllu for any f E F. Therefore, we have llqu - "= 1 I C(Eopt + Eapz + coHR (F) + coHH log (H/6)
We know
lloō 20lli.08
Σ v(also)) (80. a) - a0(
Σ (<aaso)) (7) - (T (1)00 + (T (1)( -00
a) S Σ (x)
(8) Σ (T 00(00 a)l
a,
= |l - a1ll + 11" 90ll1.05
Apply the same inequality recursively, we have
H-1
H-1
1 - -0olla.88 S
| 1 9+11 - golli.rg 1
Σ
T qh+1 qul12,d7
h=0
h=0
The last inequality follows from the Jensen's 's inequality. Therefore, have
log (H/5)
(so) Σ x (allo)))0(0 a)l s HVCCEop + Eapa + cgH + HaH2
with probability 1 5.
The bound on FQE estimate holds for one policy in the candidate set. Using the union bound, the bound can hold for all policies. Therefore, the OPS algorithm has error up to
n 2H (Eopt + Caps + c.H + cq H22 / log (1TH//5)) with probability at least 5.
A.5 DETAILS OF SECTION 4.2
By the performance difference lemma,
H
((x')-((+) = E
(Sh, An) - (Sh Th (Sw))
< E
Th An) (S Ax) (Sh, Tn (Sh)) (S(h (A()))
E"
4% (Sh. An) - (S, An)l + Ign (A(h)) (Sh, To (Sh)))
H-1
|1 ll 1, x. + 1luh 4n "ulli..g'..
H-1
17
11
qu " + 1l qu 112.0x
where dī is the state-action distribution at horizon induced by policy π. The first inequality follows because Ty is greedy with respect to qh- We consider a state-action distribution 30 that is induced by some policy, then
0196 golla.a, <
[Tq Tqi + Tq 20ll2,00
<
[Tqi - -Tqil2..s + +1 - -uuluzz -uul2.60
l94 9n m1l2,,, + C1 g0 2,40
16

---

Under review as a conference paper at ICLR 2023
where B1 (s', = =.a=d===.... Su alss, s' )lff' arg e (s', (s',"")) "=(("',a'))" is also induced by some policy. The first inequality follows by the fact that q" is the fixed point of the operator T. can recursively apply the same process for 1l% qn 12 >> O, and we can get
H
11 2n 12. SC
Σ
TThht
Th 12..
Therefore,
H-1
l1g" - 90l12,80 SCH Σ
|| - 20 900
Now we show that
log (/1)
1
Tyx 12,,0 S min l1g: Tqq 12112,, + co vovnax
holds with probability at least - 8 for some constant co.
Proof. Using Hoeffding's 's inequality and the union bound, with probability at least - 8
log (H (1)
Σ (s, - max ( 22)12 -Igi,a - Tq.,+111... S c1 By
(s,a,,,"))DD,
for all candidate value function = (g.11. qi - I,..., 11I and E [H].
Let be the index with the lowest empirical Bellman error, that is,
H
arg min
Σ
(0:(8, - max (88,' a/)12
nH
(s,a,
Then
log
11gx -Tgx x min |/: TT: co coVoman Vmaz
B EXPERIMENTAL DETAILS
We provide the experimental details in this section.
Generating candidate policies. To generate set of candidate policies, run CQL with different hyperparameter configurations on batch of data with 300 episodes collected with an e-greedy policy with respect to the optimal policy where = 0.4. The hyperparameter configuration includes:
Learning rate E (0.001, 0.0003, 0.0001}
Network hidden layer size E (128, 258, 512}
Regularization coefficient E (1.0, 0.1, 0.010 0.001,
Iterations of CQL {100,200)
That is, we have 90 candidate policies for Acrobot.
For Cartpole, CQL with many hyperparameter configurations can generate an optimal policy (reach- ing return of 200) the selection is sufficiently easy that OPS algorithms using both FQE and BE achieve zero regret. In order to make the result more meaningful, we remove all the policies that are optimal from the candidate set. That results in 67 candidate policies for Cartpole.
17

---

Under review as a conference paper at ICLR 2023
Generating offline data for OPS. To generate data for offline policy selection, ferent data distributions: (a) data distribution collected by running the mixture of all candidate policies. As result, the data distribution covers all candidate policies well; (b) data distribution collected by running the mixture of all candidate policies and an e-greedy optimal policy that pro- vides more diverse trajectories than (a); (c) data distribution collected by deterministic optimal policy.
three dif-
To perform experiment with multiple runs. To perform experiments with multiple runs, we fix the offline data and the candidate policies and only resample the offline data for OPS. This better reflects the theoretical result that the randomness is from resampling the data for an OPS algorithm. In our experiments, use runs and report the average regret with one standard error. Since the variability across runs is not large, we find using runs is enough.
Random selection baseline We include a random selection baseline that randomly chooses policies given k. Since the random selection algorithm has very high variance within run, first compute the expected regret of random selection by performing 2000 times random selection within each run, and report the average regret over runs.
Practical considerations for FQE implementation. As mentioned in the paper, we fix the function class as two layer neural network model with hidden size 256 and tune the opti- mization hyperparameters. We use the Adam optimizer with learning rate selected from the set {0.001, 0.0003, 0.0001, 0.00003} for 200 epochs. We selected the hyperparameter configuration that resulted in value function with the smallest RMSTD error evaluated separate validation dataset. To avoid selecting an uncovered policy, we assign a low estimate to policies when FQE diverges a large value.
18


Reviews:
[{"review_id": "lY4i_4xKauy", "reviewer": "Reviewer_vxfJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper presents an analysis of the problem of offline policy selection OPS. The study is motivated by the problem of hyperparameter tuning for offline RL algorithms, which is emerging as an important direction to understand in order to effectively deploy learned policies. One approach the authors study is OPS. While it is obvious that OPS is possible via OPE, the authors show, in a minimax sense, that OPS is as hard as OPE. Later, several sample complexity results are derived for OPS based on known OPE methods. Experiments are presented comparing FQE and a standard (biased) Bellman error selector", "summary_of_the_review": "I believe this paper is studying an important problem that deserves attention in the community, and it has some interesting insights and discussions as well as a lot of potential. I just think that it unfortunately falls short of the technical depth necessary for publication. In light of this, I have some suggestions that I hope will strengthen the paper for future submissions.\n- I would try to focus less on the presentation of results that are either mostly known or easily derivable given the existing literature. Examples: Theorem 3, 4 and Corollary 1. They are fine discussion topics, but I think it’s hard to argue them as original results and they detract from the real important results.\n- The result of Theorem 2 and the experiments are the most interesting parts of the paper by far. In particular, Theorem 2 opens up a flood of interesting research questions. For example, what is the true sample complexity of selecting an ‘epsilon’-best policy from a small set? Pursuit of this direction might, for example, mirror the rich literature that has emerged on best-arm identification in bandits [1, 2], despite worst-case bounds painting a fairly pessimistic picture (as Theorem 2 does here).\n\n1. Jamieson & Nowak. “Best-arm Identification Algorithms for Multi-Armed Bandits in the Fixed Confidence Setting.”\n2. Kaufmann et al. “On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models”\n", "strength_and_weaknesses": "Strengths\n- This paper studies an important and timely hyperparameter-tuning problem for the offline RL community.\n- The results of Theorem 2 suggest that OPS is as hard as OPE in the worst case.\n- There is extensive discussion of possible OPS methods leveraging OPE for sample efficient results.\n\n\nWeaknesses\n- Many of the results presented do not appear to be particularly new. While they may not have been stated exactly in the same form as presented here, I believe they share too great an overlap to overlook. Here are a few papers which, with some modifications and combinations, should be able to produce the results:\n\nCorollary 1 -> Xiao et al 2022 (which is already cited)\n\nTheorem 3 -> Dudik et al 2011 (Doubly robust policy evaluation and learning), Thomas & Brunskill (Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning)\n\nTheorem 4 -> Duan & Yang, 2020 (Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation) + Duan et al 2021 (already cited)\n\n\nMinor points:\n- The validity of Bellman error for deterministic settings has been discussed in Zhang and Jiang (2021) as well. They also have experiments with it.\n- BVFT (Xie & Jiang and Zhang & Jiang) actually does not require Q* in the set. It allows approximation error (which estimation error and approximation error of a model class can be absorbed into). There are some shortcomings of BVFT (such as slower rate, stronger distribution assumptions, etc), but its generality is very good.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZxyL4BoedsX", "reviewer": "Reviewer_H7wj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The article is a theoretical paper studying policy selection through off-policy evaluation. More precisely, the paper proposes 3 contributions: a) a theoretical analysis of the sample complexity of policy selection w.r.t the sample complexity of OPE, b) the derivation of sample complexity for Fitted Q-evaluation, and c) a similar derivation when using the Bellman error as a selection criterion. In addition, the article proposes a few experimental results to check if the provided bounds are 'valid' when facing concrete problems.\n\n", "summary_of_the_review": "In conclusion, the paper proposes interesting insight into off-policy selection, even if it is restricted to a particular setting (discrete actions + few policies to evaluate). The theoretical results connecting selection and OPE make sense, and the (too small) experimental study is validating the differences identified in the two OPE approaches that are studied. ", "strength_and_weaknesses": "First of all, the topic attacked by the article is very relevant and interesting. Being able to have better insights into the validity of the different OPE approaches for policy selection is relevant and interesting to the community. As a remark, I am not fully familiar with the theoretical literature in this particular domain and I did not check all the proofs. The way the article is written makes the contributions clear, even if the notations are a little bit dense. The defined assumptions show that the paper is restricted to a particular family of problems where i) actions are discrete and ii) the number of policies to compare is not too big which explains why the positioning is focused on hyperparameters selection. As a consequence; the results are valid only if the set of policies is not too large and cannot be used for instance when trying to find a good architecture (the experiments are indeed made on a set of 90 and 67 policies). This is a limit of the contribution. Particularly, I would be happy to have a better discussion about how the results hold when the number of possible actions is growing (As far as I understand, the sample complexity is exponential w.r.t the number of actions for OPE). Being more clear on the assumptions and discussing this point would facilitate the reading.\n\nIn addition to the sample complexity bounds between policy selection and OPE, the authors study two particular OPE algorithms and allow us to better understand what is happening when using one of these approaches as a selection criterion. These insights are then evaluated on two concrete sets of experiments achieved in two different environments. The authors study 3 different dimensions: the value of 'k' in a top-k approach, the number of needed episodes, but also the distribution of these episodes. The results do not give any advantage between BE and FQE, even if FQE seems to be a better approach in many cases. As a drawback of the analysis, the environments provided here are very simple, with very few possible actions, and I would encourage the authors to re-iterate their experimental protocol over some other benchmarks. For instance, it may be interesting to take a look at some D4RL environments (after discretization of the actions for instance), or environments like mazes (e.g minigrid?) where one could expect to have more than 2 or 3 possible actions. An unclear aspect also is the performance of a completely random selection algorithm. Particularly, we do not know the distribution of regrets over the set of learned policies, so maybe a random selection with k=10 would produce similar results. Adding these results is simple but important.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WDEu5O1Ot7e", "reviewer": "Reviewer_fS4W", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies some theoretical properties of the offline policy selection (OPS) problem. It shows that this problem's worst case (in the sense of query policy set) sample complexity is upper-bounded and lower-bounded by the sample complexity of off-policy evaluation (OPE). Thus these OPS and OPE have the same difficulty in the worst-case sense. Then this paper provides a polynomial error bound for OPS based on Fitted Q evaluation (FQE) and Bellman error when the policy set is well-covered.", "summary_of_the_review": "This paper discusses an important problem and provides some clear theoretical results. However, the provided result is too limited to give new insight into this problem.", "strength_and_weaknesses": "Strength:\n1. This paper studies an important problem for deploying offline RL algorithms, for example in the case of hyper-parameter search or model selection.\n2.  This paper provides a clear answer about the relationship between OPS and OPE, in terms of worse-case sample complexity. This is a nice result to shed the light on algorithm design and analysis.\n\nWeakness:\n1. A large part of the paper contains either existing results or a trivial extension of them. Section 3.1 may not be explicitly stated in previous work, but should be considered a well-known result in the RL area. Section 3.2's result is novel, but the main techniques in the construction exist in previous work. Section 3.3 is also not new in some sense, given the OPS <-> OPE reduction. IS is the minimax optimal OPE estimator is known (E.g. Wang et al. 2017, Optimal and Adaptive Off-policy Evaluation in Contextual Bandits.). Theorem 4 in Section 4 is based on the error bound of FQE. A very similar form of this bound, if not exactly the same, exists in many OPE or offline RL literature. The discussion on known results can be reduced to give more space to discuss new results.\n2. I like the discussion at the end of sections 3.2 and 3.3 which explains that the worst-case analysis may not be informative enough in when policy set \\Pi has a certain structure. However, this is not discussed enough later. In practice, the policies for OPS are not arbitrary most time but have a certain structure: a sequence of checkpoints during training NN, policies from different hyperparameters and may have a monotonically increasing off-policyness or OPE variance, policies from function classes with monotonically increasing capacity. To understand when is offline hyperparameter selection feasible in practical scenarios, I think it is important to analyze some policy set structure that has a connection to the practical OPS problem. Section 4 gives an assumption about the policy \\Pi, but it is a strong and uniform assumption, but not about the relationships between policies.\n3. There are many other OPE estimators besides FQE. It would increase the significance of the empirical study if authors could analyze more and their different impacts on the OPS problems.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5LOzonxHgGt", "reviewer": "Reviewer_DgEQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper tackles the question of when offline policy selection (OPS, selecting a well-performing policy in offline RL) can be performed efficiently. For this they determine bounds based on bounds by offline policy evaluation (OPE): OPS is lower-bounded by the number of samples/episodes required for OPE. The paper explores when and under which assumptions fitted Q evaluation (FQE) is suitable for OPS (when candidate policies are well-covered by the dataset) and when Bellman errors (BE) for OPS are suitable (empirically performs better than FQE with small sample size).", "summary_of_the_review": "My main concerns are the motivation, the clarity issues, making the paper hard to read, and an insight for practical use.\n", "strength_and_weaknesses": "### Strengths:\n* Theoretical analysis of the required number of episodes to perform offline policy selection (OPS) with the help of offline policy evaluation (OPE)\n\n### Weaknesses:\n* [Motivation of Hyperparameter Optimization/Selection] \nThe story of OPS for HP selection can be made stronger or adjusted altogether. My questions are:\nIs it important that the policies which should be selected from are generated from the same algorithm, just with different hyperparameters (HPs)? Because if not, then the motivation for the paper is way broader because this is relevant for general selection among policies. In this case I see the candidate policies with different examples just as an example which is easy to construct. Also, if I would want to use OPS now to select suitable HPs for offline RL, what do the results tell me in practice?\n\n* What hyperparameters are meant in the conclusion? Is it important to set up the collection of the dataset well (but how)? Or is it in general important how to set the HPs of the RL algo? Because of the latter I think this paper hinted at it briefly (we can see a large regret between the best policy from the top-k policies and best from all candidate policies, but we don’t know how bad some HP configurations are).\n* [Clarity] In fact, there are many open questions for me (see next text box) that need to be clarified. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject