Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The article is a theoretical paper studying policy selection through off-policy evaluation. More precisely, the paper proposes 3 contributions: a) a theoretical analysis of the sample complexity of policy selection w.r.t the sample complexity of OPE, b) the derivation of sample complexity for Fitted Q-evaluation, and c) a similar derivation when using the Bellman error as a selection criterion. In addition, the article proposes a few experimental results to check if the provided bounds are 'valid' when facing concrete problems.


strength_and_weaknesses: First of all, the topic attacked by the article is very relevant and interesting. Being able to have better insights into the validity of the different OPE approaches for policy selection is relevant and interesting to the community. As a remark, I am not fully familiar with the theoretical literature in this particular domain and I did not check all the proofs. The way the article is written makes the contributions clear, even if the notations are a little bit dense. The defined assumptions show that the paper is restricted to a particular family of problems where i) actions are discrete and ii) the number of policies to compare is not too big which explains why the positioning is focused on hyperparameters selection. As a consequence; the results are valid only if the set of policies is not too large and cannot be used for instance when trying to find a good architecture (the experiments are indeed made on a set of 90 and 67 policies). This is a limit of the contribution. Particularly, I would be happy to have a better discussion about how the results hold when the number of possible actions is growing (As far as I understand, the sample complexity is exponential w.r.t the number of actions for OPE). Being more clear on the assumptions and discussing this point would facilitate the reading.

In addition to the sample complexity bounds between policy selection and OPE, the authors study two particular OPE algorithms and allow us to better understand what is happening when using one of these approaches as a selection criterion. These insights are then evaluated on two concrete sets of experiments achieved in two different environments. The authors study 3 different dimensions: the value of 'k' in a top-k approach, the number of needed episodes, but also the distribution of these episodes. The results do not give any advantage between BE and FQE, even if FQE seems to be a better approach in many cases. As a drawback of the analysis, the environments provided here are very simple, with very few possible actions, and I would encourage the authors to re-iterate their experimental protocol over some other benchmarks. For instance, it may be interesting to take a look at some D4RL environments (after discretization of the actions for instance), or environments like mazes (e.g minigrid?) where one could expect to have more than 2 or 3 possible actions. An unclear aspect also is the performance of a completely random selection algorithm. Particularly, we do not know the distribution of regrets over the set of learned policies, so maybe a random selection with k=10 would produce similar results. Adding these results is simple but important.


clarity,_quality,_novelty_and_reproducibility: * The paper is well written, even if it proposes dense notations and masks a little bit the underlying assumptions . The setting could be made more clear
* The paper gives theoretical insights about techniques that people are using, and help to better understand the link between policy selection and OPE.
* Experiments are maybe too simple, and having more diverse settings and better baselines would be interesting
* It is reproducible
summary_of_the_review: In conclusion, the paper proposes interesting insight into off-policy selection, even if it is restricted to a particular setting (discrete actions + few policies to evaluate). The theoretical results connecting selection and OPE make sense, and the (too small) experimental study is validating the differences identified in the two OPE approaches that are studied.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents an analysis of the problem of offline policy selection OPS. The study is motivated by the problem of hyperparameter tuning for offline RL algorithms, which is emerging as an important direction to understand in order to effectively deploy learned policies. One approach the authors study is OPS. While it is obvious that OPS is possible via OPE, the authors show, in a minimax sense, that OPS is as hard as OPE. Later, several sample complexity results are derived for OPS based on known OPE methods. Experiments are presented comparing FQE and a standard (biased) Bellman error selector
strength_and_weaknesses: Strengths
- This paper studies an important and timely hyperparameter-tuning problem for the offline RL community.
- The results of Theorem 2 suggest that OPS is as hard as OPE in the worst case.
- There is extensive discussion of possible OPS methods leveraging OPE for sample efficient results.


Weaknesses
- Many of the results presented do not appear to be particularly new. While they may not have been stated exactly in the same form as presented here, I believe they share too great an overlap to overlook. Here are a few papers which, with some modifications and combinations, should be able to produce the results:

Corollary 1 -> Xiao et al 2022 (which is already cited)

Theorem 3 -> Dudik et al 2011 (Doubly robust policy evaluation and learning), Thomas & Brunskill (Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning)

Theorem 4 -> Duan & Yang, 2020 (Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation) + Duan et al 2021 (already cited)


Minor points:
- The validity of Bellman error for deterministic settings has been discussed in Zhang and Jiang (2021) as well. They also have experiments with it.
- BVFT (Xie & Jiang and Zhang & Jiang) actually does not require Q* in the set. It allows approximation error (which estimation error and approximation error of a model class can be absorbed into). There are some shortcomings of BVFT (such as slower rate, stronger distribution assumptions, etc), but its generality is very good.

clarity,_quality,_novelty_and_reproducibility: The paper is overall well written. However, some of the descriptions should better contextualize the results in the related work.
summary_of_the_review: I believe this paper is studying an important problem that deserves attention in the community, and it has some interesting insights and discussions as well as a lot of potential. I just think that it unfortunately falls short of the technical depth necessary for publication. In light of this, I have some suggestions that I hope will strengthen the paper for future submissions.
- I would try to focus less on the presentation of results that are either mostly known or easily derivable given the existing literature. Examples: Theorem 3, 4 and Corollary 1. They are fine discussion topics, but I think it’s hard to argue them as original results and they detract from the real important results.
- The result of Theorem 2 and the experiments are the most interesting parts of the paper by far. In particular, Theorem 2 opens up a flood of interesting research questions. For example, what is the true sample complexity of selecting an ‘epsilon’-best policy from a small set? Pursuit of this direction might, for example, mirror the rich literature that has emerged on best-arm identification in bandits [1, 2], despite worst-case bounds painting a fairly pessimistic picture (as Theorem 2 does here).

1. Jamieson & Nowak. “Best-arm Identification Algorithms for Multi-Armed Bandits in the Fixed Confidence Setting.”
2. Kaufmann et al. “On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models”
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies some theoretical properties of the offline policy selection (OPS) problem. It shows that this problem's worst case (in the sense of query policy set) sample complexity is upper-bounded and lower-bounded by the sample complexity of off-policy evaluation (OPE). Thus these OPS and OPE have the same difficulty in the worst-case sense. Then this paper provides a polynomial error bound for OPS based on Fitted Q evaluation (FQE) and Bellman error when the policy set is well-covered.
strength_and_weaknesses: Strength:
1. This paper studies an important problem for deploying offline RL algorithms, for example in the case of hyper-parameter search or model selection.
2.  This paper provides a clear answer about the relationship between OPS and OPE, in terms of worse-case sample complexity. This is a nice result to shed the light on algorithm design and analysis.

Weakness:
1. A large part of the paper contains either existing results or a trivial extension of them. Section 3.1 may not be explicitly stated in previous work, but should be considered a well-known result in the RL area. Section 3.2's result is novel, but the main techniques in the construction exist in previous work. Section 3.3 is also not new in some sense, given the OPS <-> OPE reduction. IS is the minimax optimal OPE estimator is known (E.g. Wang et al. 2017, Optimal and Adaptive Off-policy Evaluation in Contextual Bandits.). Theorem 4 in Section 4 is based on the error bound of FQE. A very similar form of this bound, if not exactly the same, exists in many OPE or offline RL literature. The discussion on known results can be reduced to give more space to discuss new results.
2. I like the discussion at the end of sections 3.2 and 3.3 which explains that the worst-case analysis may not be informative enough in when policy set \Pi has a certain structure. However, this is not discussed enough later. In practice, the policies for OPS are not arbitrary most time but have a certain structure: a sequence of checkpoints during training NN, policies from different hyperparameters and may have a monotonically increasing off-policyness or OPE variance, policies from function classes with monotonically increasing capacity. To understand when is offline hyperparameter selection feasible in practical scenarios, I think it is important to analyze some policy set structure that has a connection to the practical OPS problem. Section 4 gives an assumption about the policy \Pi, but it is a strong and uniform assumption, but not about the relationships between policies.
3. There are many other OPE estimators besides FQE. It would increase the significance of the empirical study if authors could analyze more and their different impacts on the OPS problems.
clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is very clearly written.

Quality: Proof of upper bound or construction of hard examples for lower bounds are correct. Existing results in this paper are generally solid and well organized. My main complaint is the content of this paper is not enough.

Novelty: See Strength And Weaknesses.

Reproducibility: No code provided.
summary_of_the_review: This paper discusses an important problem and provides some clear theoretical results. However, the provided result is too limited to give new insight into this problem.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper tackles the question of when offline policy selection (OPS, selecting a well-performing policy in offline RL) can be performed efficiently. For this they determine bounds based on bounds by offline policy evaluation (OPE): OPS is lower-bounded by the number of samples/episodes required for OPE. The paper explores when and under which assumptions fitted Q evaluation (FQE) is suitable for OPS (when candidate policies are well-covered by the dataset) and when Bellman errors (BE) for OPS are suitable (empirically performs better than FQE with small sample size).
strength_and_weaknesses: ### Strengths:
* Theoretical analysis of the required number of episodes to perform offline policy selection (OPS) with the help of offline policy evaluation (OPE)

### Weaknesses:
* [Motivation of Hyperparameter Optimization/Selection] 
The story of OPS for HP selection can be made stronger or adjusted altogether. My questions are:
Is it important that the policies which should be selected from are generated from the same algorithm, just with different hyperparameters (HPs)? Because if not, then the motivation for the paper is way broader because this is relevant for general selection among policies. In this case I see the candidate policies with different examples just as an example which is easy to construct. Also, if I would want to use OPS now to select suitable HPs for offline RL, what do the results tell me in practice?

* What hyperparameters are meant in the conclusion? Is it important to set up the collection of the dataset well (but how)? Or is it in general important how to set the HPs of the RL algo? Because of the latter I think this paper hinted at it briefly (we can see a large regret between the best policy from the top-k policies and best from all candidate policies, but we don’t know how bad some HP configurations are).
* [Clarity] In fact, there are many open questions for me (see next text box) that need to be clarified. 

clarity,_quality,_novelty_and_reproducibility: Quality: Theorems seem to be fine (have checked the easiest two of the proofs so not entirely sure).

Novelty: The paper shows that OPS is bounded by OPE which hasn’t been shown before; so that’s a novel and important insight.

Reproducibility: The empirical results seem not to be easily reproducible as there is no code available and no mention of what implementations have been used for the different OPEs.

Clarity: Overall, this paper wasn’t easy for me to read, although having quite some knowledge in RL and hyperparameters. In fact, it would help tremendously, if the authors would provide more intuitions and exemplary practical implications early on. 
In particular, I have some questions for understanding/regarding clarity:

* How to find out n (n >= 100 as the empirical results suggest for both FQE and BE as OPE? The more, the better, but for FQE it seems to increase for high n?)?
* Clarity Sec. 3.3: It took me way too long to figure out the example MDP, a visualization would help massively. Also, why is a_h selected via argmin of pi? Where does the ⅛ come from in Corollary 1?
* Clarity Sec. 4: It took me some time figuring out what F is (~until related work), it would be nice if it would be mentioned briefly.
Just to make sure that I got it right: the FQE estimate for J(pi) is the expected value at the initial state?
* Sec 6: Why do you think that BE performs better than FQE for expert data even though C is high? (I assume C is high because only one policy has been used to generate the data so candidate policies are not well-covered.)
* Clarity Figure 1+2: For comparability please use the same scale on the y-axis. Why is the regret for diverse data way lower than for expert and well-covered data? On which performance metrics is the regret computed? Why do you only use 5 different runs? How does the (complexity of the) environment influence the required number of samples? It looks like Acrobot needs more episodes than Cartpole (at least for top-5). Why is the regret so high in Cartpole for top-10?
* How different are the generated candidate policies / J(pi)? Because if they are very similar it does not really matter how good OPE or OPS are.
* Appendix A.1, the equation after (1): is this the correct epsilon?
* App A.2: A small figure for the MDP would also be nice, makes it clearer right at the beginning of what is happening.
Is the general assumption that V_max is known? If yes, is it stated in the main paper? Is the general assumption that the rewards are bounded, if yes, was this also stated before the appendix? How are they bounded?
* App. A.3: What is W_i?

summary_of_the_review: My main concerns are the motivation, the clarity issues, making the paper hard to read, and an insight for practical use.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the sample complexity of offline hyperparameter selection (OPS). It presents a reduction of OPS to offline policy evaluation (OPE) and vice verse, and thereby gives both an upper and lower bound of OPS using the sample complexity of OPE. It further applies a few common OPE methods to OPS and analyzes their worst case sample complexity. Empirical studies are conducted with simple experiments.

Strengths:
- Sound theoretical study on the sample complexity of OPS. This has been rarely done in prior works.
- It builds a formal connection between OPS and OPE and shows that OPS is not easier than OPE in the worst case. This could be interesting for the community.

Weaknesses:
- Multiple reviewers are concerned with the depth of the theoretical analysis. Most conclusions can be derived easier from existing results on OPE once the reduction is built. The main interesting theoretical contribution is Theorem 2 that gives the lower bound of OPS. Unfortunately, this result is not sufficiently expanded to provide useful insights and impacts the significance of Theorem 2.
- Although OPS is shown the have the same level of difficulty with OPE in the worst case, it could be easier in some particular scenarios. Exploring problem structure to discovery these problems could be particularly useful to the community.

I would encourage authors to take into account the reviews and following up discussion seriously and prepare a revision for re-submission.

justification_for_why_not_higher_score: Consensus on the lack of depth in the theoretical contribution and the worst case analysis on common OPE algorithms does not provide useful insights.
Decision: Reject