Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learning
Authors: Siyuan Zhang
Nan Jiang
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
offline RL
policy selection
hyperparameter-free

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. 

Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learning
Siyuan Zhang
Nan Jiang
Computer Science
Computer Science
University of Illinois at Urbana-Chaman Champaagn siyuan36illimg www.lllinoiieeee.e
University of Illinois Champaaign
ialaaanngnnnnniii edu
Abstract
How to select between policies and value functions produced by different training algorithms in offline reinforcement learning (RI)-which) is crucial for hyperpa- rameter 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-ege situation. In this paper, we design hyperparameter-free algorithms for policy selection based 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 hyperparameter-uun method for Q-function based OPE with theoretical guarantees as a side product.
Introduction and Related Works
Learning good policy from historical data without interactive access to the actual environment, or offline (batch) reinforcement learning (RL), is promising approach applying RL to real-world sce- narios when high-fidelity simulators are not available [LKTF20). Despite the fast development the training algorithms, burning question that remains wide open how 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 a difficult problem, and standard estimators such importance sampling suffer exponential (in horizon) variance [LS155] JL16]. While ielyyooial-vvriaane estimators exist, either using TD (e.g.. Fitted-Q Evaluation, FQE [LVY19] ) marginalized importance sampling [LLTZI8 NCDL19 UHJ20). they require additional function approximation, inducing yet another set of hyperparameters (c.g., the neural-net architecture) which need to be carefully chosen. [Pa+200] recently conclude that FQE can be effective for offline policy selection, but "an important remaining challenge is how to choose hyperparameters for FQE". (Incidentally, our approach in Section hyperparameters for OPE, creating a chicken-and-egg situation. To this end, we want to ask:
side product of other words, to tune hyperparameters for training we need to tune the
are able address this question
Can we design effective hyperparameter-ffre methods for offline policy selection?
The question has been investigated in the theoretical literature (FST). mostly reformulated so that we select indirectly among value functions instead of policies to trade-off directness for tractability. More precisely, (FSI1) imagines that training algorithms produce candidate Q-functions Q1, Q2 ..... Qm. which is reasonable assumption as most offline algorithms produce value functions as a side product. The goal is to select Q; Rs Q* assuming one exists-so that the induced greedy policy, &Q, is near-optimal. While ||Q Q*1 only a surrogate for performance of kq. the hope is that whether
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Q= Q" can be more easily verified from holdout data without additional function approximation. possibly by estimating the Bellman error (or residual) -QQI. Unfortunately, ||- is not amendable to statistical estimation in stochastic environments (SB18). The naïve estimator which squares the TD error (see "I-sample BR" in Proposition } suffers the infamous double-sampling bias [Bai95], and debiasing approaches demand additional function approximation (and hence hyperparameters) [ASMOS] [SII]. In prototypical real-world applications, hyperparameter-Tre 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 funet-funtiion selection: [XI2I] 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 - 11 where the function class for projection is created out of the candidate Q's themselves. See Section 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 (M,, 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 (T, Q) pairs and pick one where Q ~ Q" and yields a high return. To further handle the issue that Q from the critic often a poor fit of Q", we propose to use multiple OPE algorithms to re-fit Q", and run BVFT-PE among the produced (T, 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.
2 Preliminaries
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 ::3 S x A + [0, Rmax] transition function S:Sk x A + ASS) (A(-) is the probability simplex), discount factor 7 E [0, 1). and a initial state distribution do. We assume S x is finite but can be arbitrarily large. A deterministic policy : S + A induces a random trajectory so, dg, ro, 81, a1, .l.... where s0 ~ do Ge = (8t),, Tt = R(st, at), and 8t+1 P(-|st,a,) a4), Vt. We measure the performance of π using J(x) = E E -t= /rr. In discounted MDPs, there always exists an optimal policy T that maximizes J(-) for all starting states. It is the greedy policy of the optimal Q-function, Q", i.c., x* TQ- == (s + arg max, Q" (s) Q* is the fixed point of Bellman optimality equation, Q* = TQ", where fff e SxSAAA (T)) a) == R(s, a) + PP-''p(-le.. [maxæ/ f(s', aa)). A related important concept is Q-, which tells us the expected return of when the trajectory starts from 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) ~ 11, r = R(s, a), s' ~ P(-|s, a). With a slight abuse of notation, we also use [-] to denote the expectation over (8, a, s') sampled as above.
Policy Selection/Ranking We will use the following unified framework for policy selection through- out the paper: Suppose training algorithms (or the same algorithm with different hyperparameters) produce multiple (TT, Q) pairs, {(T, Q+) and our goal is select a policy with good perfor- mance. 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 म; uq., and we only need work with { 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 policy, we require all algorithms to produce ranking over { am often by sorting the policies in ascending order w.r.t. loss.
2

---

2.1 Experiment Setup
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 OpenAl Gym [Br++66]. 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 [FKNTL2I] for
MuJoCo), and generate our own otherwise by mixing trained expert policy with 30% chance of acting suboptimally. [u++21] have proposed new benchmark for offline policy selection, which is also based on RLUnplugged D4RL which we use and has only become available very recently. Also D4RL
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 offiine algorithms such as BCQ (FCGP19) and CQL [KZTL.20] 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 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 produce multiple candidate policies (and value functions) for selection; see Table Tin in Appendix C for details.
different policy-selectio methods and evaluate the produced policy rankings using the following two metrics adapted from (YDNTS20):
Performance Metries In each experiment,
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 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 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 sampling subset of the dataset for policy selection (usually of size 50, 000; FQE needs much more data and we do not run 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 TQl is an appealing quantity because Q = Q' + ||Q TQ = U. but it is not amendable to statistical estimation in stochastic environments due to the double-sampling bias [Bi99 ASM08 FSII]. Given this caveat, a closely related quantity has been extensively studied in the literature: given function class C [0, Raax R the (mean squured)) projected Bellman error of Q w.r.t. 9 defined as
1-y
||Q - T where TeQ == arg min Ep Ep - -r-- max ((s(,a)))
(I)
gEG
a'
Here -1,,,,, = [.))]. and the dependence of To on j is suppressed for readability. This quantity can be straightforwardly estimated from data when & has bounded statistical complexity; we just need to replace all I. with their finite-sample approximation. The property of the projected Bellman error largely depends the choice of G. which needs satisfy certain conditions for I|Q T to be a good surrogate for IIQ Q+ The seminal work of [Gor95] has provided the following sufficient condition: (see [XI2I] Proposition 4] for a formal proof)
Proposition If 9 a piecewise-constant class, and (2) Q' E G, then To is 7-contraction under || Iloo. and Q = Q* + I1Q ToQl12,n = 0 if μ is fully supported on S x A.
3

---

Being piecewise constant means that there exists a partitioning of S x A, and G consists of all members of [o, Bmox JSXA that remain constant within each partition. A partitioning whose induced I-x G satisfies (1) and (2) is also closely related to 1'-'Q""''PPep p'-preeerving state abstractions (LWL06).
The problem is that it is very difficult to find & that satisfies the above 2 criteria and it will just be another set of hyperparameters to tune if we leave the design of g to the user. [X121] offers a resolution in the context of selecting Q* from [Q: consider the base case of
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 91.2 that satisfies both criteria of Proposition [a the minimal
piecewise-constant class such that {Q1, Q2) C G1.2. 2. If the output of each Q; takes at most N possible values, G1,2 will be induced by partitioning S x A into at most N regions; see Figure [J22]] 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
Proposition 2 (Simplification of [J21]; see Appendix B.1 for a proof sketch). IfQ" E (Q and μ is fully supported on S x A. then Q+ Q" + Q: having 0
where
Loss( (Q1) max IQ: TT.., Qillz
3
For each Qú BVFT calculates its projected Bellman error w.r.t. Gr.- Gt.--here Gr, is created just like G1.2 but using Q; itself and every other Qn-and scores Qi using the worst-case projected error. See [XI21] for the complete theory that accounts for Q" & (Qr) and finite-sample effects. For readability we will stick to the above simplified reasoning.
The empirical version of BVFT-loss can be computed exactly in closed form. The central step is the calculation of TqQ. Recall that G is piecewise constant and induced by a S x A partitioning. For any (5, a). (5, a) is simply the average of + max.' Q(s', aa) over all data points (8, a, r, r') where (s, a) falls in the same partition as (5, a). Implemented with running averages, the computational complexity is (mm')) for m candidate functions and n data points in addition to (I-A) + 1) mm candidate-function evaluations (i.e., caching Qs Q) and max Qi(s', d')).
Computation
4 BVFT with Automatic Resolution Selection
Despite the appealing theoretical properties, it is unclear BVFT can be converted into a practical algorithm. The sample complexity of estimating BVFT- loss depends on the complexity of Gig. which is controlled by 22 where N is the number of possible values in [o, Rmaax each Q: can take. 1-7
To handle the issue that N can be very large or even infinite, [X/21] discretizes the output of (Q: 1 )m
up to Edet error before producing (9.,), ), where ddt needs to be carefully chosen to trade-off between discretization errors and the complexity of G (which is now ((1/ The theoretical value of 6dat (as in (XI2T, Theorem 2I) 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 Edct - due to the unbounded complexity of Gig-
To resolve this issue, we draw an interesting connection between BVFT-loss and the naive "1 "I-sample"
estimator for |!Q 10--77 -TQ,, I, which reveals the unexpected behavior of BVFT-loss in the regime of Edet + O that differs from the previous thcoretical predictions:
Proposition 3. Consider Eul(Q(ss a) r max, a())), the naïve and biased estimator for IIQ TQlE,n which we call "I-sample BR (Bellman residual)". If each candidate Q₂ never
'The ideal & can be created similarly to Figure I according to knowledge of Q", In Appendix D we show that our approach closely tracks the skyline of using the idcal & in a tabular domain where we can compute Q". A common misconception is that BVFT only works under the "assumption" that Q" is piccewise constant under certain given partition metric functions is used as an internal mechanism in BUFT and is not an assumption in any way. The existence 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 pre-detined metric or partition over S x A).
S X A; this is not the case. The concept of piecewise-constant
Among all the (i.j) pairs considered in WVFT-loss, many of them will not satisfy Q' E (QQ,, Q2) and thus the previous reasoning for the m = 2 case and Proposition do not apply. Despite this, these (i.j) pairs do not affect the validity of the BVFT- loss; see XJ21 for detailed explanation.
4

---

Acrobot
A Value
Q1
0.7
0.6
0.5
SKA
5.0 2scrrtiattinn. emn
Figure 1: Left: Visualization of the partitioning that induces G1.2. The 2 subsets of S x A marked orange belong to the same partition despite being separated from each other, because Q1 and Q2 are constant across them. Since 8 A is partitioned according Q's output, the number of partitions independent of |S x A), allowing BVFT to scale to arbitrarily complex state-action spaces with limited data. Right: BVFT-loss discretization error eda of 10 candidate Q's of typical run in Acrobot, all having the U-shape predicted by our theoretical reasoning.
predicts the same value for any two (s, a) pairs seen in the dataset, then with edet = 0, the empirial version of BVFT-Loss(Qi: (Q, )==1) and I-sample BR of Q2 coincide (up to squaring).
Proof. Given a dataset consisting of (s, s,a,r,s' tuples, the empirical version of 1-sample - max Q(s d'))² and that of BVFT-loss squared is (),, where To., is the empirical version of To.., based on the same dataset. suffices show that for any data point (s, as s'), (Tg., Q) a) + ymmx,' (s a'), which follows immediately from édet 0 and Q, never predicting the exact same value twice, since Gi does not provide any aggregation over data points in this case and Ta coincides with the I-sample Bellman update (c.f. the paragraph computation in Section 3
BR is 1
[D] (ean.)))) (Q(s, (Q
maxj [D E(s.an.)) (Q((,,
This result implies that, 1-sample BR, which is reasonable objective and coincides with - in deterministic environments, provides a safeguard to BVFT-loss when 6ιc is too small. Since the souble-sampling bias of 1 1-sample BR is positive [Bai95]. expect BVFT-loSS to gradually decrease as Gςs increases, hit a minimum, and increase again due to discretization errors when 6dat becomes too large Indeed, this is precisely what we observe empirically; see Figure
Based on this novel observation, we propose to search for a grid of discretization errors BVFT and pick the resolution that minimizes the loss (Eq, see pscudocode 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 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 {Q:) based on their average value on the data. "Random" ranks the policies in a completely random manner. BVFT and 1-sample BR rank (Q: in ascending order of their loss functions, respectively. The experiments are done on 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 I-sample BR? Perhaps surprisingly, BVFT deviates significantly from the behavior of I-sample BR, and almost always outperforms the latter by a wide margin. This is particularly interesting CartPole and Pendulum, where the deterministic dynamics make --samlle BR an unbiased estimate of ||Q TQII, 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 version of Taxi where we can compute I|Q TQII as skyline; see Appendix
"This be violated in extreme cases; Appendix A for details.
5

---

Asterixx-00
Breakout-vD
Pong-vO
Spacelnvaders-40
10p Crodzzinn
92-
24
24
26
24
14
40
V4
10
14
14
100 Kotonno 1omaabeee rogee
0.30
421
Random
sample BR
Avg(
BVFT
BVFT best rC5
Figure 2: Top-k metrics of policy rankings vs. & in Atari. Row shows top-k precision (the higher the better), and Row 2 shows top-k regret (the lower the better). Training algorithms are BCQ with different hyperparameters. The dataset for policy selection has 50,000 transition, which is an order of magnitude less than needed by FQE in Atari (see FQE in Enduro (VLJY19). as well as Figure 4).
Acrobot-v1
Cartpole-vl
Pendulum-vO
LunarLander-22
3.1
94-
32-
63-
0.1
04
38-
6..
0.3
04-
34-
32-
Random
sample BR
Avgo
BVFT
BVFT-best-res
Figure 3: Results in Gym control problems. The dataset for policy selection has 50,000 transitions.
Is our resolution selection rule effective? To examine the effectiveness of our resolution selection rule, we compare 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 resolu- tion selection closely tracks the performance of BVFT-best-res indistinguishable-iinn -inihaabbbeiiiiiiiiinign.n that our resolution selection rule is near-op
the extent that they are mostly
Comparison AvgQ. The simple heuristic of picking with the highest predicted value-which is sometimes used in prototypical applications (GGMVS20)-00 can be surprisingly effective sometimes, such as in Pendulum, LunarL.ander, 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 in Acrobot and Seaquest, and is much less robust compared BVFT.
One may wonder AvgQ works better with pessimistic training algorithms: if every Q: is an under- estimation 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 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 have fair comparisons with OPE-based

---

Asterix-vO
Breakout-v0
Pong-VO
Seaquest-vo
Spaceinvaders-v0
0.80
57-
34-
63
015
10
35
X2-
Figure 4: Comparison to FQE on Atari games. The figures show top-2 metrics vs, sample sizes. We did not test FQE on small sample sizes since the trend of performance degradation is clear.
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 Figure 4 shows the ranking metrics 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 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 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
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-fiee 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 parameterized policy म, and the actor π is in turn improved based on Q. The trained (T,, Q) pair in general does not satisfy x =Q, so it seems unwise to ignore ग and only focus on Q in policy selection. On related note, arg max. is often expensive not infeasible to calculate in continuous action spaces, so need to make changes to BVFT anyway.
More importantly. the success of BVFT relies on the existence of reasonable approximation of Q' among the candidate functions, which does not always hold especially for actor-critic algo- rithms. Indeed, in the Mujoco experiments shown Figure we observe poor performance of all hyperparameter-fii 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 as we will explain subsequenty-requiring us to take a multi-step approach to address one factor at time.
Step 1: BVFT-PE and BVFT-PE-Q for Joint Selection of ( Q) We first address the issue that arg max, may be infeasible to calculate in continuous-actioo domains, and that both π and Q need to be taken into consideration for actor-critic algorithms. To address this issue, we propose a variant
'Despite recent exciting developments in marginalized importance sampling (MIS), FQE often shows strong empirical performance thanks to simplicity [VLJY19 Pai+20 Fu+21]. whereas MIS not as off-the-sler shelf due to difficult optimization, so we defer the comparison as well as combining BVFT with MIS to future work.
'The recent OPE benchmarks Pai++20 Fu+21 do not include Atari, so choose hyperparameters.
7

---

HalfCheetah-v22
Hopper-y3
Walker2d-v2
811
10
10
35
39
15
80
34
43
62-
Aego
Figure 5: Top-k metrics vs. k across 3 Mujoco domains with continuous actions. All methods use dataset of size 50, 000, except that the FQE component of any method uses 10
of BVFT, called BVFT-PE, with the following loss function:
BVFT-PE-1oss(Mr: Qa): ((TTT Q,)); max QQ: TT,,, Qilla,
(3)
where Pig exactly the same as BVFT, and T5. is the same as Eq.(T) except that max. Q(s', a') should be replaced by Q(s', (s))). (In actor-critic algorithms, и is often stochastic policy, in which case the term means ()) [Q(s', a))].) This loss function naturally generalizes the BVFT-loss: when each n, is the greedy policy of Qi. we immediately have To Qi To.., Qi thus recovering BVFT-loss as a special case.
A closer inspection of Eq. 3 reveals an interesting fact: PP---PE- Q:)) = 0 as long Q: Q"1 BVFT-PE-loss is really 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 more generally there can exist the degenerate cases of Q Q but itself being a poor policy, where BVFT-PE-loss/ (T, Q)) is still O. We address this issue by subtracting Q term from the BVFT-PE-loss: BVFT-PE-Q == BVFT-PE-loss - AIE [Q). and the structure of this loss resembles telescoping identity for J commonly used in the OPE literature; see Appendix A.l for details.
TQ.
Step 2: Re-fitting Q with OPE The above derivations address some of the basic thcoretical issues, but still implicitly assume that at least one good म; is paired with Q; x Q In actor-critic algorithms, however, we often observe that the actor и converges way before the critic Q does, leaving with a poorly estimated Q. Indeed, we have already seen in Figure that BVFT-PE and BVFT-PE-Q are still not effective when applied to the candidate (T, 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 more accurate value function. We implement this using FQE as the OPE algorithm, though in principle we can use any OPE algorithm that provides estimate of Q*, including kernel loss [FLL19]. MQL [UH220], or even a model-based method through planning. Figure 5 shows that BVFT-PE and BVFT-PE- enjoy strong empirical performance. However, the bascline of simply ranking the policies according to FQE itself ("FQE+Avg"") is equally effective, which suggests that most of the performance gains should be attributed to FQE. That said, even if one's 's conclusion is that "OPE-based policy selection more superior in continuous-action domains", we are just all the way back to where started in Section[]:
How tune the hyperparametters 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
8

---

HalfCheotah-v2
Hopper-v3
Walker22dv22
Normalized NSE FQE's esúmations
HGr videe 20s 1e-4
FOE modee 294 2e-3
FIEE nisden 1024
0.4-
HoTCherrah V2
Hopperv)
Waleedd-2
A1 2000
Figure 6: Left: Policy selection with multiple FQE instances in Mujoco. To avoid cluttering, show the range of FQE performance across different hyperparameters (with upper and lower bounds connected by vertical dashed lines), and have removed error bars from HalfCheetah for better visibility (their widths are similar to the other two figures). The curves are cluttered in HalfCheetah and both strategies perform similarly to the upper bound. Right: OPE accuracy for using BVFT-PE for hyperparameter tuning in FQE, where ((T) is approximated by Es-do [s)))
each policy, producing m x L candidate (x, Q) pairs in total, in the form of {(T;, Q)),, where Q is the estimation of Q by the 1-th OPE algorithm. There two strategies can proceed with:
Strategy 1:
Run BVFT-PE-Q on all m pairs of (T,, Q). Rank the m policies according to their highest position in the ranking produced by BVFT-PE-Q.
Strategy 2: Within each T. use BVFT-PE select Q Q", then rank the policies based on the predictions of O (e.g., using AvgQ).
Applicability Arbitrary Training Algorithms We motivated BVFT-PE and BVFT-PE-Q by actor- critic training and assumed that training algorithms must produce (vr, Q) pairs. However, the approaches proposed above be readily applied any training algorithms: 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 with multiple instances of FQE using different hyperparameters (see legend of Figure 6 The results shown in Figure [ 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 merely 2mm numbers), matching the best FQE performance is strong evidence for BVFT algorithms' model selection capabilities. Between the two BVFT strategies, Strategy (using BVFT-PE-Q) Q) slightly outperforms Strategy 2, but comes with an additional hyperparameter X; 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 advantage.
Hyperparameter Tuning in OPE In Strategy 2, we are basically using OPE as the policy-selection algorithm, and BVFT-PE 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, conduct additional experiments in Mujoco to test the OPE accuracy of FQE with different hyperparameters. As Figure 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
subroutine for hyperparameter tuning for OPE itself. Since OPE
'eere the training algorithms are BCQ. In Appendix D we reproduce Figure 6 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 fixed T, which follows from similar proof techniques as [X]2T] Theorem 2); see Appendix for the proof.
Theorem 4. Let C be the same as in [XJ2] Theorem 21, which characterizes the exploratoriness of the data distribution. Consider any policy π and candidate Q-functions, {Q' with Q' E [0, 1-q! J. Let (TT, Q) be the pair that minimizes the empirical version of BVFT-PB- loss applied to (
{(TT. Q')1=11 with Edet = <Rmux. Then, using a dataset size Ô
Ca [n(
where Ô suppresses
(11)))>
logarithmic terms, w.p. 2 1 1-166, 6, suPmil///nlsss I1 - 12 I c. Bmax + (2+4vC) ming 11Q' QQ" 10o
1-7
1-7
As the theorem implies, when one of (Q")(= is good approximation of Q" (i.e., min/ 1| Q 1o is small), BVFT-PE is able to identify Q ~ Q" with a polynomial sample complexity.
Discussion and Conclusion
We present BVFT and its variants based on recent theoretical advances XJ21 which are (nearly) hyperparameter-free algorithms for policy selection in offine RL and empirically effective in discrete- action benchmarks. When combined with OPE algorithms such as FQE, variants of BVFT are also competitive in continuous-acteo 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 S usess 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 deep RL is not available. How to improve the sample efficiency of BVFT + OPE is an important open question.
Computational Complexity The O(m)) complexity of BVFT can be prohibitive if we wish to compare hundreds of models. A plausible solution is wevidc-and-conuuee i.c., climinating 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 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 RZMJRTT XCIMA2T]- when the data coverage is seriously lacking. This can be, however, quite challenging, as BVFT uses a dynamic function space for projection (Gi,)) that varies from candidate to candidate, and states considered covered due to generalization effects under one function space may be considered lacking data under different one. How 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 19----117- NSF (IS-21124711 and Adobe Data Science Research Award.
References
[ASM08]
András Antos, Csaba Szepesvári, and Rémi Munos. "Learning near-optimal policies with sellman-residual minimization based fitted policy iteration and single sample path". In: Machine Learning 71.1 (2008), pp. 89-
10

---

[Bai95]
Leemon Baird. "Residual algorithms: Reinforcement learning with function approxi- mation". In: Machine Learning Proceedings 1995. Elsevier, 1995, pp. 30-37. Mare Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. "The arcade learning environment: An evaluation platform for general agents". In: Journal of Artificial Intelligence Research 47 (2013), pp. 253-279.
[BNVB13]
[Bro+16]
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. 2016. eprint: arXiv: 1606. 01540 Jinglin Chen and Nan Jiang. innoommttion-Thoorttee
[CJ19]
Theoretic Considerations in Batch Re- inforcement Learning". In: Proceedings of the 36th International Conference Machine Learning. 2019, pp. 1042-1051.
[Die00]
Thomas G Dietterich. "Hierarchical reinforcement learning with the MAXQ value function decomposition". In: Journal of artificial intelligence research 13 (2000), pp. 227-303.
(FCGP19]
Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau. Bench- marking Batch Deep Reinforcement Learning Algorithms. 2019. arxiv: 19100 01708
[cs. LC]
[FKNTL21]
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL:
Datasets for Deep Data-Driven Reinforcement Learning. 2021. arXiv: 200:400040.170 07219
[cs.LG] [G]]
[FLL19]
Yihao Feng. Lihong Li, and Qiang Liu. "A kernel loss for solving the bellman equation". In: Advances in Neural Information Processing Systems. 2019, pp. 15430- 15441.
[FMP19]
Scott Fujimoto, David Meger, and Doina Precup. Off-Policy Deep Reinforcement Learning without Exploration. 2019, arXiv: 1812. 02900 [ca. LG]
[FS11]
Amir-massoud Farahmand and Csaba Szepesvári. "Model selection in reinforcement learning". In: Machine learning 85.3 (2011), pp. 299-332.
[FSM10]
Farahmand, Csaba Szepesvári, and Rémi Munos. "Error Propagation
for Approximate Policy and Value Iteration". In: Advances in Neural Information Processing Systems. 2010, pp. 568-576.
[Fu+21]
Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang, Alexander Novikov, Mengjiao Yang, Michael R Zhang, Yutian Chen, Aviral Kumar, et al. "Benchmarks for Deep Off-Policy Evaluation". In: arXiv preprint arXiv:2103.1 163.16666 (2021).
[GGMVS20]
Diksha Garg, Priyanka Gupta, Pankaj Malhotra, Lovekesh Vig, and Gautam Shroff. Canth--onstrriined Distributional Reinforcement Learning for Session-based Recom- mendation". In: arXiv preprint arXiv:20/2.0892: (2020).
[Gor95]
Geoffrey J Gordon. "Stable function approximation in dynamic programming" In: Proceedings of the tweifth international conference on machine learning. 1995, pp. 261-268.
[Gul+21]
Caglar Gulcehre, Ziyu Wang, Alexander Novikov, Tom Le Paine, Sergio Gomez Cohmenarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cos- min Paduraru, Gabriel Dulac-Arood, Jerry Li, Mohammad Norouzi, Matt Hoffman, Ofir Nachum, George Tucker, Nicolas Heess, and Nando de Freitas. RL Unplugged: A Suite of Benchmarks for Offline Reinforcement Learning. 2021. arxiv: 2006 13888
[cs. LG]
[JL16]
Nan Jiang and Lihong Li. "Doubly robust off-policy value evaluation for reinforce-
ment learning". In: International Conference on Machine Learning. PMLR. 2016,
pp. 652-661.
[JYW20]
Ying Jin, Zhuoran Yang, and Zhaoran Wang. "Is Pessimism Provably Efficient for Offline RL?" In: arXiv preprint 3 (2020).
[KRNJ20]
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. "Morel: Model-based offline reinforcement learning". In: arXiv preprint 2005000 (2020).
[KZTL20]
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. "Conservative q- learning for offline reinforcement learning". In: arXiv preprint arXiv:2006.047) (2020).
11

---

[LKTF20] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. "Offline reinforcement learning: Tutorial, review, and perspectives on open problems". In: arXiv preprint arXiv:2005.0 043 (2020).
[LLTZ18] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. "Breaking the curse of off- off-policy estimation". In: Advances in Neural Information Processing Systems. 2018, pp. 5361-5371.
horizon: Infinite-horee
[LMS15]
Lihong Li, Rémi Munos, and Csaba Szepesvári. "Toward Minimax Off-policy Value Estimation". In: Proceedings of the 18th International Conference on Artificial Intel- ligence and Statistics. 2015.
[LSAB19]
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. "Off-policy pol- icy gradient with state distribution correction". In: arXiv preprint arXiv: 08443 (2019).
[LSAB20]
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. "Provably Good Batch Reinforcement Learning Without Great Exploration" In: arXiv preprint DrXiv:2007088200 (2020).
[LVY19]
Hoang M. Lc, Cameron Voloshin, and Yisong Yue. Batch Policy Learning under Constraints. 2019. arXiv: 1903. 08738 (cs.LG)
[LWL06]
Lihong Li, Thomas Walsh, and Michael L Littman. "Towards a unified theory of state abstraction for MDPs". " In: Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics. 2006, pp. 531-539.
[Mni+15]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. "Human-level control through deep reinforcement learning". In: nature 518.7540 (2015), pp. 529-533.
[NCDL19]
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections. 2019, arXiv: 1906
04733 [CS.LG]
[Pai+20]
Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. "Hyperparameter selection for offline reinforcement learning". In: arXiv preprint WiXiv22007.09055 (2020). Paria Rashidinejad, Banghua Zhu, Cong Ma. Jiantao Jiao, and Stuart Russell. "Bridg- ing Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism". In: arXiv preprint arXiv:2103, /202/ (2021).
[RZMJR21]
[SB18]
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[TET12]
Emanuel Todorov, Tom Erez, and Yuval Tassa. "MuloCo: physies engine for -baee control". In: 2012 JEEE/RSJ International Conference Intelligent Robots and Systems. 2012, pp. 5026-5033. DOI: [0. 1110/IRRSSS 2012. 6386109 Masatoshi Uehara, Jiawei Huang, and Nan Jiang. "Minimax weight and q- q-function learning for off-policy evaluation". In: International Conference on Machine Learning. PMLR. 2020, pp. 9659-9668.
[UHJ20]
[UIJSXX1]]
Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. "Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency". In: arXiv preprint urXiv:2102.0296 (2021).
[VLJY19]
Cameron Voloshin, Hoang M Lc, Nan Jiang, and Yisong Yue. "Empirical study of off off-policy policy evaluation for reinforeement lcarning". In: arXiv preprint 1xXiv:111.06833 (2019).
[XCJMA21]
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal, "Bellmaan-consistent Pessimism for Offline Reinforcement Learning.. In: arXiv preprint arXiv:2 106.06926 (2021).
[X]21]
Tengyang Xie and Nan Jiang. "Batch value-function approximation with only realiz- ability". In: International Conference on Machine Learning. PMLR. 2021, pp. 11404 11413.
[YDNTS20]
Mengjiao Yang, Bo Dai, Ofir Nachum, George Tucker, and Dale Schuurmans. "Offline Policy Selection under Uncertainty". In: arXiv preprint arXiv:2012.06991 (2020).
12


Reviews:
[{"review_id": "u56fokVxZA", "reviewer": "Reviewer_8caC", "summary": "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. \n \nThis 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. \n", "questions": "", "limitations": "", "rating": 9, "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": " \nThe paper is written with exceptional clarity, where the authors provided both theoretical and experimental results backing their claim. Since there is no prior work on hyperparameter-less OPE, the authors chose a reasonable way to compare with other OPE baselines, where the baseline hyperparameters are finetuned on one set of environments and evaluated on another. The proposed method also took into consideration practical cases, such as 1. the state or action space is continuous 2.$(\\pi, Q)$ pair is not trained till the optimum, where either the policy is not greedy w.r.t. Q, or the Q is under-trained before the policy converges.  \n \nThis is a significant work that will allow OPE to have more wide-spread use in practice where hyperparameter sweeps are expensive or infeasible. It is novel both compared to BVFT and to other OPE algorithms, providing both theoretical guarantees and practical flexibility (e.g. giving the option of BVFT-PE and BVFT-PE-Q depending on whether the user is able to tune one extra hyperparameter either online or on a similar environment.)\n \nMinor nit-picking:\n1. l88. ... to test more than 1 policies -> … to test more than 1 policy\n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations of their method and either remedies or future research directions in the paper. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "p8AZZa6KHM", "reviewer": "Reviewer_s3ZC", "summary": "This paper focuses on a hyperparameter-free policy selection for offline reinforcement learning. The authors suggests two methods: (1) a automatic value-function selection method for discrete action spaces using Batch Value Function Tournament (BVFT), (2) a combination of OPE algorithms and BVFT variants for continuous action spaces (BVFT-PE, BVFT-PE-Q, ...)", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "Offline policy selection is an important problem for deploying offline reinforcement learning algorithms to many practical real-world problems. However, previous methods using off-policy policy evaluation (e.g. FQE) also require hyperparameter tuning, which makes a chicken-and-egg situation. This paper tackles this issue in a principled way using BVFT, which is the value function selection method with theoretically advanced Bellman error estimates. This paper has strong motivations and the methods are appropriate. Hence, I vote for the acceptance to this paper. I have following questions for this paper:\n\n1. In line 267, BVFT-PE-Q loss uses a hyperparameter $\\lambda$ which adjusts a penalization coefficient of the average critic value. (maybe hence the authors call their methods as \"nearly\"-hyperparameter-free in Section 6) How is $\\lambda$ choiced for the experiment and how sensitive? \n\n2. How many FQE instances are used for multi-FQE experiments (Figure 5L)? (maybe described as $L$ in the paper). I think it will be good to show that a choice of L does not significantly affect the result of experiment.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "iVtA87DQdIg", "reviewer": "Reviewer_bSdg", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "Off-policy evaluation of RL is indeed an important open question for Offline RL. The authors address it with a novel method, with extensive comparison to the existing OPE methods and some other natural approaches based on quantities like Bellman Residual, Average Q value, etc.\n\nThe clarity of this paper is ok but could be improved. I appreciate the thoughtful writing with little typos. The authors often try to ask questions then answer them. But sometimes the answer is not supported with convincing evidence.\n\nMoreover, the authors provide some theoretical properties of their BVFT algorithm. In particular, Proposition 2 which proves the equivalence between BVFT-loss and Bellman residual is interesting. However, it is not very clear how this relates to the BVFT in implementation (I see the authors provide some discussion, but giving more augmentation or insight would enhance the flow of logic).\n\nHere are some confusions/suggestions:\nOn the experiment part, using the 2 quantities top-k regret and top-k precision as the evaluation score is straightforward and considerate. But it would be more clear if the authors provide a discussion on their (different) meaning alongside the definition. (I would have some explanations on these quantities but I am not sure if the authors have the same thought.) \nTo study the variance, the authors also consider the randomness introduced by datasets. It would also be good to consider randomness introduced by the algorithm training process (initialization and SGD).\nBCQ and CQL are both experimented on the Atari benchmark, but I wonder why the authors just consider BCQ on Mujoco? These 2 offline RL algorithms are substantially different and it would be interesting to see comprehensive results of both.\nSome of the algorithmic discussion in the appendix could be moved to the main paper, while some derivations in Sections 3 and 4 could be moved to the appendix, if they are not essential for understanding the main idea of the algorithm. It would also be good if the authors provide more discussion on the intuition of their approach.\n\n*post-rebuttal*:\nI thank the authors for their detailed reply. I think it would be good for to include\n\nI think this paper studies an important question and is illuminating in some sense. I consider raising the score if the above are addressed.\n\n*\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In section 6 the authors have addressed most of the limitations of their work. One additional limitation is that their method would mostly be restricted to policy selection for Q-learning based algorithms. Though this includes a large family of offline RL approaches, imitation learning based, or model based algorithms also achieve promising results in the offline RL problem, and are worth studying. The authors could try to discuss how to extend BVFT on addressing these algorithms.\n\nThe BVFT algorithm differs from previous OPE methods in the idea and implementation, and achieves SOTA performance on discrete control benchmarks. But to avoid performance degradation in continuous control, the authors combine BVFT and OPE. Despite some advantages over OPE, this introduces additional complexity into the implementation and makes it unclear which part contributes to a promising policy selection. As for offline RL algorithms, the need for distributional constraint or value pessimism is concentrated on continuous control tasks. The situation is more interesting here, and the paper could have provided more insight. Nevertheless, it would be more significant if there is a unified approach that performs consistently well across discrete and continuous control benchmarks.\n\nI don’t see any potential negative societal impact of this work.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns from my side.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "VJDdpqBHVuJ", "reviewer": "Reviewer_qEm2", "summary": "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.\n", "questions": "", "limitations": "", "rating": 8, "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": "To me the paper ranks quite highly in terms of originality - it can be seen as a relatively simple extension of an existing approach, but as I mentioned in the summary the extension is quite clever and seems to work really well on some problems and is well motivated. I also found the  paper very good in terms of quality and clarity\n\nIn terms of significance, I think the authors should explore more what kind of domains their approach can be really helpful in. My feeling is that it will be less useful in domains where complex function approximators are required for learning good policies, and their approach to continuous action space policy selection seems a bit complex for widespread practical use to me, plus it introduces lambda which is a hyperparameter that probably needs tuning (although the approach is interesting). I do think however that there is at least one important application area that looks perfectly suited for their approach, and that is OPE / policy selection from clinical trial data - see e.g. Raghu, A., Komorowski, M., Celi, L. A., Szolovits, P., and Ghassemi, M. (2017) Continuous state-space models for optimal sepsis treatment: a deep reinforcement learning approach. This is because the data there is limited but piecewise continuous value functions are likely to work well there, and also be more interpretable than neural approximations. I encourage the authors to explore this direction if they find it interesting.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I appreciate the authors pointing out one of the major limitations of their work - “the success of BVFT relies on the existence of a reasonable approximation of Q* among the candidate functions”, and the fact that they explore (and to some extent address) the limitations in the context of continuous action spaces. And while I understand why this is not included in the paper, I definitely encourage the authors to try and produce results using the benchmarks in [Fu+21].\n\nAs mentioned in the main review, I think using this type of approach with clinical trial data for adaptive treatment regimes could have considerable positive societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The manuscript examines the question of how to improve policy selection in the off-line RL setting. Typically offline policy selection is approached via off-policy evaluation (OPE), aimed at estimating the expected return of candidate policies. OPE is itself a difficult problem that typical requires hyperparameter tuning and selection itself. The paper develops moves closer to a hyperparameter-free method and demonstrates the effectiveness of the algorithm in the context of standardized offline datasets (e.g. RLUnplugged for Atari).
The algorithm for policy selection is built using insights from the recently published Batch Value-Function Tournament (BVFT) approach to estimating the best value function from among a set of candidates.
They make comparisons to well developed OPE style methods such as fitted Q-evaluation and show clear advantages in data efficiency and the policy selection.
The manuscript examines applying the approach to a wide range of settings (from Atari to continuous control) and to a range of policies produced by a variety of algorithms. The ideas, theory, and experiments are well motivated by the text. Taken together, the manuscript provides a promising look at a fundamental and open problem in RL. 

Decision: Accept (Poster)