Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learning
Year: 2021

Abstract:
How to select between policies and value functions produced by different training algorithms in offline reinforcement learning (RL)—which is crucial for hyperparameter tuning—is an important open question. Existing approaches based on off-policy evaluation (OPE) often require additional function approximation and hence hyperparameters, creating a chicken-and-egg situation. In this paper, we design hyperparameter-free algorithms for policy selection based on BVFT [XJ21], a recent theoretical advance in value-function selection, and demonstrate their effectiveness in discrete-action benchmarks such as Atari. To address performance degradation due to poor critics in continuous-action domains, we further combine BVFT with OPE to get the best of both worlds, and obtain a hyperparameter-tuning method for Q-function based OPE with theoretical guarantees as a side product.

heading: 1 Introduction and Related Works
text: Learning a good policy from historical data without interactive access to the actual environment, or offline (batch) reinforcement learning (RL), is a promising approach to applying RL to real-world scenarios when high-fidelity simulators are not available [LKTF20]. Despite the fast development in the training algorithms, a burning question that remains wide open is how to tune their hyperparameters, sometimes known as the offline policy selection problem [Pai+20; YDNTS20; Fu+21].
Standard approaches reduce the problem to off-policy evaluation (OPE), which estimates the expected return of the candidate policies and choose accordingly. Unfortunately, OPE itself is a difficult problem, and standard estimators such as importance sampling suffer exponential (in horizon) variance [LMS15; JL16]. While polynomial-variance estimators exist, either using TD (e.g., Fitted-Q Evaluation, or FQE [LVY19]) or marginalized importance sampling [LLTZ18; NCDL19; UHJ20], they require additional function approximation, inducing yet another set of hyperparameters (e.g., the neural-net architecture) which need to be carefully chosen. [Pai+20] recently conclude that FQE can be effective for offline policy selection, but “an important remaining challenge is how to choose hyperparameters for FQE”. (Incidentally, we are able to address this question as a side product of our approach in Section 5.) In other words, to tune hyperparameters for training we need to tune the hyperparameters for OPE, creating a chicken-and-egg situation. To this end, we want to ask:
Can we design effective hyperparameter-free methods for offline policy selection?
The question has been investigated in the theoretical literature [FS11], mostly reformulated so that we select indirectly among value functions instead of policies to trade-off directness for tractability. More precisely, [FS11] imagines that training algorithms produce candidate Q-functions Q1, Q2, . . . , Qm, which is a reasonable assumption as most offline algorithms produce value functions as a side product. The goal is to select Qi ≈ Q?—assuming one exists—so that the induced greedy policy, πQi , is near-optimal. While ‖Q−Q?‖ is only a surrogate for the performance of πQ, the hope is that whether
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Q ≈ Q? can be more easily verified from holdout data without additional function approximation, possibly by estimating the Bellman error (or residual) ‖Q− T Q‖. Unfortunately, ‖Q− T Q‖ is not amendable to statistical estimation in stochastic environments [SB18]. The naïve estimator which squares the TD error (see “1-sample BR” in Proposition 3) suffers the infamous double-sampling bias [Bai95], and debiasing approaches demand additional function approximation (and hence hyperparameters) [ASM08; FS11]. In prototypical real-world applications, hyperparameter-free heuristics such as picking the highest Q [GGMVS20] are often used despite the lack of theoretical guarantees, which we will compare to in our experiments.
In this paper, we attack the problem based on a recent theoretical breakthrough in value-function selection: [XJ21] propose a theoretical algorithm, BVFT, which provides a workaround to the double sampling issue without requiring additional function approximation; they estimate a form of projected Bellman error as a surrogate for ‖Q−Q?‖, where the function class for projection is created out of the candidate Q’s themselves. See Section 3 for details. Our contributions are 2-fold:
1. We design a practical implementation of BVFT based on novel theoretical observations, removing its last hyperparameter which determines a discretization resolution. We empirically demonstrate that BVFT enjoys promising performance in discrete-action benchmarks such as Atari games, sometimes using 20x less data than required by FQE-based policy selection.
2. The vanilla BVFT suffers performance degradation in continuous-action benchmarks, where the training algorithms often have an actor-critic structure and output a (π,Q) pair where Q is far away from Q? for various reasons. To address this challenge, we propose BVFT-PE, a variant of BVFT that allows us to select among (π,Q) pairs and pick one where Q ≈ Qπ and π yields a high return. To further handle the issue that Q from the critic is often a poor fit of Qπ, we propose to use multiple OPE algorithms to re-fit Qπ , and run BVFT-PE among the produced (π,Q) pairs. While the OPE algorithms often have many hyperparameters that need to be set, BVFT-PE automatically chooses between them, leaving very few to no hyperparameters untunable. This allows us to combine the strengths of OPE and BVFT and get the best of both worlds. We also show additional results that BVFT-PE can be used for hyperparamter tuning in Q-function-based OPE and provide theoretical guarantees, which is of independent interest.

heading: 2 Preliminaries
text: Markov Decision Processes (MDPs) In RL, we often model the environment as an MDP, specified by its state space S, action space A, reward function R : S × A → [0, Rmax], transition function P : S ×A → ∆(S) (∆(·) is the probability simplex), discount factor γ ∈ [0, 1), and a initial state distribution d0. We assume S×A is finite but can be arbitrarily large. A deterministic policy π : S → A induces a random trajectory s0, a0, r0, s1, a1, r1, . . . where s0 ∼ d0, at = π(st), rt = R(st, at), and st+1 ∼ P (·|st, at), ∀t. We measure the performance of π using J(π) := E[ ∑∞ t=0 γ
trt|π]. In discounted MDPs, there always exists an optimal policy π? that maximizes J(·) for all starting states. It is the greedy policy of the optimal Q-function, Q?, i.e., π? = πQ? := (s 7→ arg maxaQ?(s, a)). Q? is the fixed point of Bellman optimality equation, Q? = T Q?, where ∀f ∈ RS×A, (T f)(s, a) := R(s, a) + γEs′∼P (·|s,a)[maxa′ f(s′, a′)]. A related important concept is Qπ, which tells us the expected return of π when the trajectory starts from a specific state-action pair.
Offline Data In offline RL, we are given a dataset of (s, a, r, s′) tuples and cannot directly interact with the MDP. For the theoretical part of the paper, we assume the standard offline sampling protocol, that the tuples are generated i.i.d. as (s, a) ∼ µ, r = R(s, a), s′ ∼ P (·|s, a). With a slight abuse of notation, we also use Eµ[·] to denote the expectation over (s, a, r, s′) sampled as above. Policy Selection/Ranking We will use the following unified framework for policy selection throughout the paper: Suppose training algorithms (or the same algorithm with different hyperparameters) produce multiple (π,Q) pairs, {(πi, Qi)}mi=1, and our goal is to select a policy with good performance. The relationship between π and Q can differ in different contexts: for example, when training algorithms try to fit Q? and induce a greedy policy, we have πi = πQi , and we only need to work with {Qi}mi=1 as they contain all the relevant information. In the case where training algorithms have an actor-critic structure, π and Q are separate quantities and need to be reasoned about together. In real applications, the next step in the pipeline is to deploy the policy in the real system for online evaluation, and since we may have the resources to test more than 1 policy, we require all algorithms to produce a ranking over {πi}mi=1, often by sorting the policies in ascending order w.r.t. a loss.

heading: 2.1 Experiment Setup
text: To avoid interrupting the flow of intertwined theoretical reasoning and empirical evaluation in the rest of the paper, we briefly describe our experiment setup here, with details deferred to Appendix C.
Environments and Datasets We perform empirical evaluation on OpenAI Gym [Bro+16], Atari games [BNVB13], and Mujoco [TET12]. Taxi [Die00] is used for sanity check. We use standard offline datasets when available (RLUnplugged [Gul+21] for Atari, and D4RL [FKNTL21] for MuJoCo), and generate our own otherwise by mixing a trained expert policy with 30% chance of acting suboptimally. [Fu+21] have proposed a new benchmark for offline policy selection, which is also based on RLUnplugged/D4RL which we use and has only become available very recently. Also this benchmark (and [VLJY19]) focuses on OPE and policy selection without value functions, which does not exactly fit our purposes. We leave the evaluation on their benchmarks to future work.
Training Algorithms We use several different training algorithms to generate the candidate models, including offline algorithms such as BCQ [FCGP19] and CQL [KZTL20]. To test the robustness of the policy-selection methods w.r.t. how the candidate policies are generated, we also use algorithms that learn from online interactions such as DQN [Mni+15] in some domains, though policy selection is always performed using separate offline datasets. This scenario is also of interest in its own right, as one can imagine training on (possibly imperfect) simulators via online algorithms and using limited realworld offline data for policy selection. For each algorithm, we consider different neural architectures, learning rates, and learning steps as hyperparameters to produce multiple candidate policies (and value functions) for selection; see Table 1 in Appendix C for details.
Performance Metrics In each experiment, we run different policy-selection methods and evaluate the produced policy rankings using the following two metrics adapted from [YDNTS20]:
Top-k normalized regret We take the best policy within the top-k recommended by the ranking, and calculate its gap compared to the best policy among all candidates. This metric reflects our regret if we were to online-evaluate the top-k policies in the ranking and identify the best among them. To make the value more interpretable, we normalize the regret by the gap between the best and the worst candidate policies. Top-k precision We take the k best policies in terms of their groudtruth values, and return the proportion of them appearing in the top-k policies in the ranking.
This process is repeated for 200 or 300 runs, with randomness coming from re-sampling a subset of the dataset for policy selection (usually of size 50, 000; FQE needs much more data and we do not run it on random subsets) and sampling m = 10 or 15 policies from all candidates for comparison. All figures report the mean with error bars of twice the standard errors, i.e., 95% confidence intervals.
3 Background: Batch Value-Function Tournament (BVFT)
We briefly introduce the theoretical basis of our approach. As mentioned in Section 1, the Bellman error ‖Q − T Q‖ is an appealing quantity because Q = Q? ⇔ ‖Q − T Q‖∞ = 0, but it is not amendable to statistical estimation in stochastic environments due to the double-sampling bias [Bai95; ASM08; FS11]. Given this caveat, a closely related quantity has been extensively studied in the literature: given function class G ⊂ [0, Rmax1−γ ]
S×A, the (mean-squared) projected Bellman error of Q w.r.t. G is defined as
‖Q− TGQ‖22,µ, where TGQ := arg min g∈G Eµ[(g(s, a)− r − γmax a′ Q(s′, a′))2]. (1)
Here ‖ · ‖22,µ = Eµ[(·)2], and the dependence of TG on µ is suppressed for readability. This quantity can be straightforwardly estimated from data when G has bounded statistical complexity; we just need to replace all Eµ[·] with their finite-sample approximation. The property of the projected Bellman error largely depends on the choice of G, which needs to satisfy certain conditions for ‖Q− TGQ‖ to be a good surrogate for ‖Q − Q?‖. The seminal work of [Gor95] has provided the following sufficient condition: (see [XJ21, Proposition 4] for a formal proof)
Proposition 1. If (1) G is a piecewise-constant class, and (2) Q? ∈ G, then TG is γ-contraction under ‖ · ‖∞, and Q = Q? ⇔ ‖Q− TGQ‖2,µ = 0 if µ is fully supported on S ×A.
Being piecewise constant means that there exists a partitioning of S × A, and G consists of all members of [0, Rmax1−γ ]
S×A that remain constant within each partition. A partitioning whose induced G satisfies (1) and (2) is also closely related to Q?-preserving state abstractions [LWL06]. The problem is that it is very difficult to find G that satisfies the above 2 criteria,1 and it will just be another set of hyperparameters to tune if we leave the design of G to the user. [XJ21] offers a resolution in the context of selecting Q? from {Qi}mi=1: consider the base case of m = 2 where we only need to select between Q1 and Q2. If one of them is Q? (which can be relaxed) but we do not know which, we can still create G1,2 that satisfies both criteria of Proposition 1 as the minimal piecewise-constant class such that {Q1, Q2} ⊂ G1,2. If the output of each Qi takes at most N possible values, G1,2 will be induced by partitioning S ×A into at most N2 regions; see Figure 1L.2 [XJ21] further shows that this idea extends to arbitrary m via pairwise comparison (“tournament”): The validity of the procedure can be justified by the following simplified result:3
Proposition 2 (Simplification of [XJ21]; see Appendix B.1 for a proof sketch). If Q? ∈ {Qi}mi=1 and µ is fully supported on S ×A, then Qi = Q? ⇔ Qi having 0 BVFT-loss, where
BVFT-loss(Qi ; {Qj}mj=1) := max j ‖Qi − TGi,jQi‖2,µ. (2)
For each Qi, BVFT calculates its projected Bellman error w.r.t. Gi,j—where Gi,j is created just like G1,2 but using Qi itself and every other Qj—and scores Qi using the worst-case projected error. See [XJ21] for the complete theory that accounts for Q? /∈ {Qi}mi=1 and finite-sample effects. For readability we will stick to the above simplified reasoning.
Computation The empirical version of BVFT-loss can be computed exactly in closed form. The central step is the calculation of TGQ. Recall that G is piecewise constant and induced by a S ×A partitioning. For any (s̃, ã), (TGQ)(s̃, ã) is simply the average of r + γmaxa′ Q(s′, a′) over all data points (s, a, r, s′) where (s, a) falls in the same partition as (s̃, ã). Implemented with running averages, the computational complexity is O(m2n) for m candidate functions and n data points in addition to (|A|+ 1)mn candidate-function evaluations (i.e., caching Qi(s, a) and maxa′ Qi(s′, a′)).
4 BVFT with Automatic Resolution Selection
Despite the appealing theoretical properties, it is unclear if BVFT can be converted into a practical algorithm. The sample complexity of estimating BVFT-loss depends on the complexity of Gi,j , which is controlled by N2 where N is the number of possible values in [0, Rmax1−γ ] each Qi can take. To handle the issue that N can be very large or even infinite, [XJ21] discretizes the output of {Qi}mi=1 up to dct error before producing {Gi,j}, where dct needs to be carefully chosen to trade-off between discretization errors and the complexity of G (which is now O(1/ 2dct)). The theoretical value of dct (as in [XJ21, Theorem 2]) not only relies on unknown properties of the MDP and the data, but is also very small which makes BVFT-loss expensive to estimate. Indeed, the previous theory predicts that BVFT-loss becomes an unstable statistic when dct → 0 due to the unbounded complexity of Gi,j . To resolve this issue, we draw an interesting connection between BVFT-loss and the naïve “1-sample” estimator for ‖Q − T Q‖, which reveals the unexpected behavior of BVFT-loss in the regime of dct → 0 that differs from the previous theoretical predictions: Proposition 3. Consider Eµ[(Q(s, a) − r − γmaxa′ Q(s′, a′))2], the naïve and biased estimator for ‖Q − T Q‖22,µ which we call “1-sample BR (Bellman residual)”. If each candidate Qi never
1The ideal G can be created similarly to Figure 1 according to knowledge of Q?. In Appendix D we show that our approach closely tracks the skyline of using the ideal G in a tabular domain where we can compute Q?.
2A common misconception is that BVFT only works under the “assumption” that Q? is piecewise constant under certain given partition or metric over S × A; this is not the case. The concept of piecewise-constant functions is used as an internal mechanism in BVFT and is not an assumption in any way. The existence of G1,2 is unconditional and does not rely on any structural properties of the underlying MDP. Constructing the partition (and hence G1,2) only requires Q1 and Q2, and does not require any additional prior knowledge (including but not limited to a pre-defined metric or partition over S ×A).
3Among all the (i, j) pairs considered in BVFT-loss, many of them will not satisfy Q? ∈ {Qi, Qj} and thus the previous reasoning for the m = 2 case and Proposition 1 do not apply. Despite this, these (i, j) pairs do not affect the validity of the BVFT-loss; see [XJ21] for a detailed explanation.
predicts the same value for any two (s, a) pairs seen in the dataset, then with dct = 0, the empirial version of BVFT-loss(Qi; {Qj}mj=1) and 1-sample BR of Qi coincide (up to squaring).
Proof. Given a dataset D consisting of (s, a, r, s′) tuples, the empirical version of 1-sample BR is 1|D| ∑ (s,a,r,s′)∈D(Q(s, a) − r − γmaxa′ Q(s′, a′))2, and that of BVFT-loss squared is
maxj 1 |D| ∑
(s,a,r,s′)∈D(Q(s, a) − (T̂Gi,jQ)(s, a))2, where T̂Gi,j is the empirical version of TGi,j based on the same dataset. It suffices to show that for any data point (s, a, r, s′), (T̂Gi,jQ)(s, a) = r + γmaxa′ Qi(s
′, a′), which follows immediately from dct = 0 and Qi never predicting the exact same value twice, since Gi,j does not provide any aggregation over data points in this case and T̂Gi,j coincides with the 1-sample Bellman update (c.f. the paragraph on computation in Section 3).
This result implies that, 1-sample BR, which is a reasonable objective and coincides with ‖Q− T Q‖ in deterministic environments, provides a safeguard to BVFT-loss when dct is too small. Since the double-sampling bias of 1-sample BR is positive [Bai95], we expect BVFT-loss to gradually decrease as dct increases, hit a minimum, and increase again due to discretization errors when dct becomes too large.4 Indeed, this is precisely what we observe empirically; see Figure 1R.
Based on this novel observation, we propose to search for a grid of discretization errors in BVFT and pick the resolution that minimizes the loss (Eq.(2)); see pseudocode in Appendix A. In the experiments we will always use this rule to automatically select the discretization resolution for BVFT and its variants. The remaining questions can only be answered empirically: Does BVFT ever exhibit more interesting behavior than 1-sample BR (especially given their intimate relationship), is our resolution selection rule a good one, and how does BVFT compare to other baselines?
Empirical Evaluation To answer these questions, we empirically compare BVFT, 1-sample BR, and another simple hyperparameter-free heuristic, AvgQ [GGMVS20], which simply ranks {Qi}mi=1 based on their average value on the data. “Random” ranks the policies in a completely random manner. BVFT and 1-sample BR rank {Qi}mi=1 in ascending order of their loss functions, respectively. The experiments are done on 5 Atari games (Figure 2) and 4 Gym control problems (Figure 3; action space is made discrete in Pendulum).
• Does BVFT ever exhibit more interesting behavior than 1-sample BR? Perhaps surprisingly, BVFT deviates significantly from the behavior of 1-sample BR, and almost always outperforms the latter by a wide margin. This is particularly interesting in CartPole and Pendulum, where the deterministic dynamics make 1-sample BR an unbiased estimate of ‖Q− T Q‖, and we expected it to perform well. Contrary to our expectation, 1-sample BR performs poorly even in these domains, where BVFT often performs much better. In fact, we observe similar phenomenon in a version of Taxi where we can compute ‖Q− T Q‖ as a skyline; see Appendix D.
4This can be violated in some extreme cases; see Appendix A for details.
• Is our resolution selection rule effective? To examine the effectiveness of our resolution selection rule, we compare to a skyline of BVFT itself (“BVFT-best-res”), where the best fixed resolution is chosen based on average statistics in the hindsight. As we can see, BVFT with automatic resolution selection closely tracks the performance of BVFT-best-res—to the extent that they are mostly indistinguishable—indicating that our resolution selection rule is near-optimal.
• Comparison to AvgQ. The simple heuristic of picking Q with the highest predicted value—which is sometimes used in prototypical applications [GGMVS20]—can be surprisingly effective sometimes, such as in Pendulum, LunarLander, and Pong. BVFT performs equally well in these domains. Moreover, as results from other domains reveal, AvgQ is very unstable and can fail catastrophically, such as in Acrobot and Seaquest, and is much less robust compared to BVFT.
One may wonder if AvgQ works better with pessimistic training algorithms: if every Qi is an underestimation of the true return, then maximizing Q will be a well-justified heuristic. However, such pessimism is not always guaranteed especially when the function approximation is misspecified. In Appendix D we show additional experiments in Atari with a pessimistic algorithm CQL, and the results are qualitatively similar to Figure 2.
Comparison to OPE Despite the lack of known method for tuning OPE’s hyperparameters except for “cheating” in the simulator using online roll-outs (in Section 5 we will combine BVFT with OPE to address this issue), which makes it very difficult to have fair comparisons with OPE-based
policy-selection methods, it is still instructive to have a rough sense of how our method compares to OPE. In this and the next sections, we choose Fitted Q-Evaluation (FQE) as a representative OPE algorithm.5 Figure 4 shows the ranking metrics vs. sample size in 5 Atari games. We tune the neural architecture for FQE by choosing the training architecture that produces the best policy in Asterix.6 While FQE has equally good performance compared to BVFT in the large-sample regime (106 transitions, which is typically required for FQE in Atari), the performance degradation is severe when sample size decreases. In comparison, BVFT is much more sample-efficient and provides almost the same level of performance with about 20x less samples, which is also what we used in Figure 2.
Additional Results In Appendix D we examine the sensitivity of different methods to the dataset size and exploratoriness. BVFT remains advantageous compared to the baselines, is insensitive to data exploratoriness, and enjoys improved performance when more data becomes available unlike other hyperparmeter-free baselines.
5 Fighting Poor Value-Function Estimates with BVFT + OPE
The experiments so far are on discrete-action domains, and the candidate policies are always greedy w.r.t. the Q-function. However, in continuous-action domains, actor-critic-type algorithms are often used, where a critic Q is trained to evaluate a parameterized policy π, and the actor π is in turn improved based on Q. The trained (π,Q) pair in general does not satisfy π = πQ, so it seems unwise to ignore π and only focus on Q in policy selection. On a related note, arg maxa′ is often expensive if not infeasible to calculate in continuous action spaces, so we need to make changes to BVFT anyway.
More importantly, the success of BVFT relies on the existence of a reasonable approximation of Q? among the candidate functions, which does not always hold especially for actor-critic algorithms. Indeed, in the Mujoco experiments shown in Figure 5, we observe poor performance of all hyperparameter-free methods, including variants of BVFT for continuous-action domains we develop later, and no method can consistently outperform the trivial baseline of random ranking. We address this issue of poor critics in the rest of this section. The issue is quite complicated and has many contributing factors—as we will explain subsequently—requiring us to take a multi-step approach to address one factor at a time.
Step 1: BVFT-PE and BVFT-PE-Q for Joint Selection of (π,Q) We first address the issue that arg maxa′ may be infeasible to calculate in continuous-action domains, and that both π and Q need to be taken into consideration for actor-critic algorithms. To address this issue, we propose a variant
5Despite recent exciting developments in marginalized importance sampling (MIS), FQE often shows strong empirical performance thanks to its simplicity [VLJY19; Pai+20; Fu+21], whereas MIS is not as off-the-shelf due to its difficult optimization, so we defer the comparison as well as combining BVFT with MIS to future work.
6The recent OPE benchmarks [Pai+20; Fu+21] do not include Atari, so we choose our own hyperparameters.
of BVFT, called BVFT-PE, with the following loss function:
BVFT-PE-loss((πi, Qi) ; {(πj , Qj)}mj=1) := max j ‖Qi − T πiGi,jQi‖2,µ, (3)
where Gi,j is exactly the same as in BVFT, and T πiGi,j is the same as Eq.(1), except that maxa′ Q(s ′, a′) should be replaced by Q(s′, π(s′)). (In actor-critic algorithms, π is often a stochastic policy, in which case the term means Ea′∼π(·|s′)[Q(s′, a′)].) This loss function naturally generalizes the BVFT-loss: when each πi is the greedy policy of Qi, we immediately have T πiGi,jQi = TGi,jQi, thus recovering BVFT-loss as a special case.
A closer inspection of Eq.(3) reveals an interesting fact: BVFT-PE-loss((πi, Qi)) = 0 as long as Qi = Qπi , so BVFT-PE-loss is really a loss function for policy evaluation, hence the name BVFT-PE. (We will actually provide the theoretical guarantees of BVFT-PE for policy evaluation at the end of this section; see Theorem 4.) While the loss recovers BVFT-loss when π = πQ, more generally there can exist the degenerate cases of Q = Qπ but π itself being a poor policy, where BVFT-PE-loss((π,Q)) is still 0. We address this issue by subtracting a Q term from the BVFT-PE-loss: BVFT-PE-Q := BVFT-PE-loss− λEµ[Q], and the structure of this loss resembles a telescoping identity for J(π) commonly used in the OPE literature; see Appendix A.1 for details.
Step 2: Re-fitting Q with OPE The above derivations address some of the basic theoretical issues, but still implicitly assume that at least one good πi is paired with a Qi ≈ Qπi . In actor-critic algorithms, however, we often observe that the actor π converges way before the critic Q does, leaving us with a poorly estimated Q. Indeed, we have already seen in Figure 5 that BVFT-PE and BVFT-PE-Q are still not effective when applied to the candidate (π,Q) pairs.
A natural solution to the problem is to use OPE algorithms to refit Qπ to replace the critic Q, in order to provide a more accurate value function. We implement this using FQE as the OPE algorithm, though in principle we can use any OPE algorithm that provides an estimate of Qπ , including kernel loss [FLL19], MQL [UHJ20], or even a model-based method through planning. Figure 5 shows that BVFT-PE and BVFT-PE-Q enjoy strong empirical performance. However, the baseline of simply ranking the policies according to FQE itself (“FQE+AvgQ”) is equally effective, which suggests that most of the performance gains should be attributed to FQE. That said, even if one’s conclusion is that “OPE-based policy selection is more superior in continuous-action domains”, we are just all the way back to where we started in Section 1:
How can we tune the hyperparameters for OPE itself?
Step 3: Re-fitting Q with Multiple OPE Algorithms Our last idea is retrospectively simple, yet allows us to combine the strengths of BVFT and OPE and get the best of both worlds. Suppose we have L OPE algorithms which we wish to select from. We will simply run each OPE algorithm on
each policy, producing m× L candidate (π,Q) pairs in total, in the form of {(πi, Qli)}, where Qli is the estimation of Qπi by the l-th OPE algorithm. There are two strategies we can proceed with:
Strategy 1: Run BVFT-PE-Q on all m× L pairs of (π,Q). Rank the m policies according to their highest position in the ranking produced by BVFT-PE-Q.
Strategy 2: Within each πi, use BVFT-PE to select Q l?i i ≈ Qπ, then rank the policies based on the predictions of Ql ? i i (e.g., using AvgQ).
Applicability to Arbitrary Training Algorithms We motivated BVFT-PE and BVFT-PE-Q by actorcritic training and assumed that training algorithms must produce (π,Q) pairs. However, the approaches proposed above can be readily applied to any training algorithms: we discard the Q from training in Step 2, and therefore the training algorithms do not need to produce value functions in the first place.
Empirical Evaluation We use these strategies in the same experiment setting as Figure 5, with multiple instances of FQE using different hyperparameters (see legend of Figure 6R).7 The results are shown in Figure 6L, where both strategies perform similarly to or better than the best FQE instance. We emphasize that this is highly nontrivial, because BVFT-PE and BVFT-PE-Q do not observe the identities of the FQE algorithms across different policies and runs (in fact, each FQE algorithm is represented as merely 2mn numbers), so matching the best FQE performance is strong evidence for BVFT algorithms’ model selection capabilities. Between the two BVFT strategies, Strategy 1 (using BVFT-PE-Q) slightly outperforms Strategy 2, but comes with an additional hyperparameter λ; we tuned it on Hopper and use the same constant in all experiments. In comparison, Strategy 2 is only slightly worse and does not have its own hyperparameters, which is an advantage.
Hyperparameter Tuning in OPE In Strategy 2, we are basically using OPE as the policy-selection algorithm, and BVFT-PE as a subroutine for hyperparameter tuning for OPE itself. Since OPE is an important component of the offline RL pipeline in its own right, our procedure for tuning OPE algorithms using BVFT-PE is also of independent interest. To this end, we conduct additional experiments in Mujoco to test the OPE accuracy of FQE with different hyperparameters. As Figure 6R shows, FQE with hyperparameters tuned by BVFT-PE consistently outperforms the best fixed set of hyperparameters across all 3 Mujoco domains. This implies that BVFT-PE can select the best hyperparameters for each policy individually, which is an appealing property. We also supplement the
7Here the training algorithms are BCQ. In Appendix D we reproduce Figure 6L with CQL as the training algorithms; see Figure 8. The results are qualitatively the same.
empirical results with a theoretical guarantee for selecting Qπ out of candidate functions for a fixed π, which follows from similar proof techniques as [XJ21, Theorem 2]; see Appendix B for the proof. Theorem 4. Let C be the same as in [XJ21, Theorem 2], which characterizes the exploratoriness of the data distribution. Consider any policy π and candidate Q-functions, {Ql}Ll=1, with Ql ∈ [0, Rmax1−γ ]. Let (π, Q̂) be the pair that minimizes the empirical version of BVFT-PE-loss applied to
{(π,Ql)}Ll=1 with dct = Rmax 8 √ C . Then, using a dataset of size Õ ( C2 ln(L/δ) 4(1−γ)4 ) where Õ suppresses
logarithmic terms, w.p.≥ 1−δ, supν:‖ν/µ‖∞≤C ‖Q̂−Q π‖2,ν ≤ · Rmax1−γ +
(2+4 √ C)minl ‖Ql−Qπ‖∞
1−γ .
As the theorem implies, when one of {Ql}Ll=1 is a good approximation ofQπ (i.e., minl ‖Ql−Qπ‖∞ is small), BVFT-PE is able to identify Q̂ ≈ Qπ with a polynomial sample complexity.

heading: 6 Discussion and Conclusion
text: We present BVFT and its variants based on recent theoretical advances [XJ21], which are (nearly) hyperparameter-free algorithms for policy selection in offline RL and empirically effective in discreteaction benchmarks. When combined with OPE algorithms such as FQE, variants of BVFT are also competitive in continuous-action benchmarks, and such a combination addresses the weaknesses of BVFT (relying on the existence of good value functions among the candidates) and those of OPE (having untunable hyperparameters) and gets the best of both worlds.
We conclude the paper with discussions of the limitations of our approach and open questions:
Sample Efficiency Section 5 uses OPE to fit Qπ , which can be data intensive. A plausible solution is to re-use the training data for OPE, as suggested by [Pai+20]. However, data reuse can cause serious issues in realworld domains where the amount of training data taken for granted in deep RL is not available. How to improve the sample efficiency of BVFT + OPE is an important open question.
Computational Complexity The O(m2) complexity of BVFT can be prohibitive if we wish to compare hundreds of models. A plausible solution is divide-and-conquer, i.e., eliminating bad models by running BVFT in smaller groups. It will be interesting to see if this compromises performance.
Applicability It is important to understand what type of domains BVFT is particularly suited for. Despite having provided partial answers (e.g., the discussion of discrete actions vs. continuous actions), we still need a more thorough answer based on comprehensive evaluation across more diverse domains and comparison to a wider range of baselines, which is beyond the scope of this paper since we focus on algorithm development and some of our contributions are orthogonal to existing approaches (e.g., BVFT + OPE). We look forward to investigating this question empirically in the future with the help of the public benchmarks that have become available recently [Fu+21].
Data with Insufficient Coverage While results in Appendix D show that BVFT is insensitive to moderate changes in data exploratoriness, we will likely need to incorporate some form of pessimism– which is shown to be important for training [LSAB19; LSAB20; KRNJ20; JYW20; RZMJR21; XCJMA21]—when the data coverage is seriously lacking. This can be, however, quite challenging, as BVFT uses a dynamic function space for projection (Gi,j) that varies from candidate to candidate, and states considered covered due to generalization effects under one function space may be considered lacking data under a different one. How to resolve this issue and design a pessimistic version of BVFT is an interesting question.
Acknowledgments and Disclosure of Funding
Nan Jiang acknowledges funding support from the ARL Cooperative Agreement W911NF-17-2-0196, NSF IIS-2112471, and Adobe Data Science Research Award.

Review summaries:
Batch Value Function Tournament (BVFT) is an existing approach to offline policy selection that uses piecewise linear value function approximations and selects the policy with the smallest projected Bellmane error in that space. This paper automatically selects the BVFT value function resolution by using a clever argument involving the convergence of the projected Bellman error to the regular Bellman error when the resolution goes to zero. On datasets from Atari and Gym datasets this approach is very close to selecting the best resolution in retrospect. They also show how this approach can be extended to policy gradient methods for continuous actions, where the application of BVFT is less straightforward than in discrete action spaces. 

The paper proposed a new method Batch Value-Function Tournament (BVFT) for the off-policy evaluation of RL. The algorithm is hyperparameter-free thus could be applied to a variety of Offline RL algorithms. Experiments are conducted on both discrete and continuous control benchmarks. BVFT outperforms other baselines on some Atari (discrete control) environments but cannot match OPE methods on the Mujoco (continuous control) environments. The authors further consider a method combining BVFT and OPE. This method is able to tie with the performance OPE on Mujoco and has some nice properties. In addition to empirical results, the authors also provide theories to support their method. 

Offline Policy Evaluation (OPE) is when one needs to choose the best policy within a set of policies given only access to an offline dataset. Most OPE algorithms relies on function approximation and thus has hyperparameters. Previous works showed promising performance when the hyperparameters are tuned “online”, thus limiting their use case in practice. This paper proposes a way to select hyperparameters using purely the given offline dataset.    This paper expands on BVFT and turns it into a practical OPE algorithm without hyperparameters. More specifically, it proved that the BVFT-loss in its limit is equivalent to the naive estimator of the Bellman residual (which is biased in a stochastic environment). When one chooses a reasonable discretization resolution, experimentally BVFT performs better than the naive estimator. When the environment is continuous, the authors proposed to combine BVFT with FQE or other hyperparameter-dependent OPE methods. The experiments showed that the proposed method often matches or outperforms existing OPE algorithms.