Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol

We thank the reviewer for appreciating the contributions of our work and the helpful comments for improvement.

 

---

Why is picking a single model a good idea? ensemble?

First, it is not clear what "ensemble" of models means in the context of OPE: do we simply average the final prediction? or we average the transition dynamics (like in [MJTS20]?) How do we weight each model? We are not aware of widely accepted ways of using ensemble in the context of OPE.

Second, there are ways to reduce the "ensemble" idea to our setting. In particular, if by "ensemble" we mean averaging transitions (like [MJTS20]), then an ensemble of "base MDPs" is simply a well-defined MDP itself. There is no reason why one cannot add such a model to $\mathcal{M}$. Furthermore, if the weights for averaging "base" models are unknown, we may also consider $\mathcal{M}$ to be a set of models with different weights. That said, if the unknown weight space is continuous, this is more of a learning problem than a model selection problem, as our methods are not computationally efficient for continuous $\mathcal{M}$. A plausible solution is to run other methods to learn such ensemble models in a separate learning phase, and apply our method in the selection phase.

 

[MJTS20] Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles.

 

---

Model-based (MB) approaches: "ad hoc", "out of the blue", "out-done by model-free"

The motivation for considering MB is that it has access to more available information than MF algorithms (if you have $\mathcal{M}$, you can induce the value functions, but not vice versa), so it is natural to expect that by leveraging the additional information in $\mathcal{M}$ one can potentially do better than MF. This is what we expected before running the experiments, and it was surprising to see that LSTD-tournament works better than the MB methods, which we find interesting to report.

As another side product, we wanted to compare to [ZDMAK23], which is one of the very few existing methods for MF selection. However, they require a helper function class in addition to $\mathcal{Q}$. The regression-based algorithm is essentially a clever way to implement [ZDMAK23], where the helper class ($\mathcal{G}\_i$) can be constructed from $\mathcal{M}$.

---

the [MB] bounds seem fairly large/loose

I was disappointed that the authors left [comparison between MF and MB guarantees] to future work

Ok this is a very tricky question. The MB guarantees (Theorems 4 and 5) are actually very standard (Line 230R). You can find very similar analyses in the OPE literature under the standard "Bellman completeness" assumptions for function approximation ([XJ21;XCJMA21]). The reviewer described these bounds as "loose", but these are really the dream results (in terms of cleanness and interpretability) you would want in RL theory. We obtain them thanks to the additional information available in $\mathcal{M}$.

What is more "unusual" is Theorem 2 for LSTD-Tournament, which is largely a direct corollary of Theorem 1, the guarantee of LSTDQ. The key differences between Theorems 4,5 vs 1,2 is the definition of coverage: Theorems 4 and 5 use the standard $C^\pi$ (called "concentrability" [AMS08]), whereas Theorem 1 and 2 uses a matrix singular value that is highly specialized to LSTDQ. As far as we know, how to properly characterize the behavior of this value as a coverage parameter and how it compares to $C^\pi$ are largely open questions.

While we would certainly like to study this question, it is a fundamental issue that exists at a much more basic level. That is, you can ask the same question without even talking about model selection: just consider 3 basic OPE algorithms for learning $Q^\pi$:

1. FQE (under Bellman completeness)
2. LSTDQ (under realizability)
3. Abstraction (under $Q^\pi$-irrelevance, which is realizability for piecewise-constant class)

Their guarantees can be found in the literature, which depend on different coverage parameters. Again, no one knows how they compare. Both LSTDQ and abstraction have very algorithm-specific definitions of coverage that are very hard to parse and interpret. [JRSW24] recently made progress in understanding it for abstraction and BVFT ("aggregated concentrability"), showing it can be exponentially worse than $C^\pi$ in some cases (but there are also trivial cases where it's much better). The situation for LSTDQ and LSTD-tournament is likely similar.

[JRSW24] Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data.

So without delving further into this rabbit hole, let us just say that this comparison is a conceptual mess, and a clean and elegant answer might not even exist. Your review expressed "disappointment" which seems a pretty strong sentiment, so we want to offer an explanation.

We thank the reviewer for the comments. We do not find major concerns in the review - can you let us know what are the main factors that lead to your "weak reject"?

 

---

Importance sampling (IS)

We do not consider IS-based OPE. Vanilla IS does not need any function approximation, which is a major source of hyperparameters (e.g., neural architecture for TD). Its variants, such as doubly-robust, require a Q-function as control variates, which can be selected using our methods.

 

---

How realistic...to induce candidate value functions from "variations of the groundtruth environment"?

Great question; we intended to discuss in conclusion had we had more space. In practice, we will likely get candidate value functions by running methods like TD (say different neural architectures). When they produce inaccurate Q-functions, the errors are likely not that "uniform" compared to our generations (when we change the gravity, it changes in the same way in every state). Varying environment in more complex ways (e.g., only change gravity in certain regions) may mitigate this problem, which we leave for future investigation.

In fact, prior works have explored generating candidate Qs by FQE with different architectures, which we also tried in an early stage. The problem, as discussed on Line 80 left and Ft 1, is that often times all candidates are poor: Unlike in reality where we can devote much time to the problem at hand and come up with good candidate architectures, here we run a lot of experiments and simply don't have the energy to tailor candidate architectures to each problem instance. This is why we switched to the current protocol. While somewhat "unrealistic", its ability to carefully control the level of misspecification is an outstanding strength. Of course, it would be nice to perform empirical evaluation using both protocols if one has enough computation.

---

Are we assuming the "blackbox base algorithms" (which can be MC or TD etc)...produce the “correct” Q functions, like an oracle?

What do you mean by "correct"? If you mean that every base algorithm must produce the correct $Q\_{M^\star}^\pi$, then that's certainly not the case, otherwise the selection is trivial. On the other hand, we do have the assumption (Line 101 Right) $Q^\pi = Q\_{M^\star}^\pi \in \{\mathcal{Q}\}$ for theoretical derivations, which means that one of the base algorithms must produce the true Q-function. As long as that's the case, other base algorithms can produce arbitrary functions that need not be "correct" in any sense. Extension to the case where only a good approximation of $Q^\pi$ can be found in $\{\mathcal{Q}\}$ is routine in RL theory (Line 95 Right), and we also explore this empirically in the "misspecification" experiments (which is partly why we include it despite the lack of "trends", to answer your other question).

---

L171, $\epsilon$

$\epsilon$ refers to the RHS of the bound in Theorem 2, and solving for $n$ we have $n=O(1/\epsilon^2)$. This is a standard sample-complexity discussion and we will clarify that.

---

Reward model in MB?

We assume true reward is known in derivation and experiments for simplicity, but it is a trivial extension to allow for candidate models to have different reward models.

---

but that doesn't necessarily suggest that smaller regression error is better, especially...dataset...may lack coverage

You are absolutely right. The role of coverage is reflected in the $C^\pi$ term in Theorem 4, which a standard way to characterize data coverage (see [CJ19;LVY19]). If data lacks coverage, $C^\pi$ will be large and the guarantee vacuous. Note that this will be an issue for every method. When data lacks coverage, OPE and its model selection will be fundamentally hard. Therefore, pretty much the only thing we can do is to come up with algorithms where $Q^\pi$ (or $M^\star$ in the model-based setting) has $0$ (or minimal) loss, and typically you would have a guarantee (like Theorem 4) when certain coverage assumptions are satisfied. Also note that, $Q^\pi$ (and $M^\star$, resp.) is not even a loss-minimizer in TD-sq in Eq.2 (and mb_naive in Eq.6, resp.), which prevent them from enjoying such guarantees. So, the motivation for designing the regression-based estimators, as well as any other estimator (this is also the case for prior work like BVFT [XJ21]), is to achieve guarantees like Theorems 1,4,5, which are nontrivial.

---

L326 Expensive

We have brief big-Oh discussion on L382L, but "expensive" here is more of a numerical one. The major cost in Q-caching is simulation steps and policy calls (neural-net inference). For MF.G, the cost is data size (3200) * trajectories (128) * horizon (1024) * target policies (10) * candidate models (15) * $M^\star$ choices (3) ≈ 10^11. Runs for a few days ~ a week on a 4090 PC.

We thank the reviewer for the comments. The main criticisms arise from technical misunderstandings, which we clarify first.

---

Major Technical Misunderstandings

Comparing ...MF.G (g=-30, $\sigma$=100.0) and MF.N (g=-30, $\sigma$=100.0) give vastly different results even though the basic setup should be exactly the same.

As mentioned clearly in Section 5.1, an experiment is determined by the groundtruth $M^\star$ and the candidate model set $\mathcal{M}$, among other elements. The two experiments mentioned by the reviewer coincide in $M^\star$=(g=-30, $\sigma$=100.0), but differ crucially in $\mathcal{M}$: MF.G uses the "gravity grid" ($\mathcal{M}\_g$), and MF.N uses the "noise grid" ($\mathcal{M}\_n$); see Section 6.1. Algorithms generally behave differently when they are given different $\mathcal{M}$.

the remaining 12 experiments...are not reported.

If the reviewer thinks there must be 15 experiments because $|\mathcal{M}\_g|=15$, then that's incorrect. In Figure 2 top (MF.G), all 3 plots correspond to the same $\mathcal{M}\_g$ but 3 different $M^\star$.

---

 

[Varying noise levels creates] just a "fuzzy" version of the "ground truth" environment.

We respectfully disagree. In RL, dynamics is formally defined by the transition function $P(s'|s,a)$. Models with the same gravity but different noise levels have different $P(s'|s,a)$, so they are technically different.

While describing them as "fuzzy versions" of the same MDP is neither rigorous nor helpful, the reviewer is perhaps concerned that they may be roughly the same, which makes the experiments in MF.N trivial. This is simply not the case in Figure 2. Had all the models in MF.N ($\mathcal{M}\_n$) be roughly the same, all methods would have nearly 0 OPE error, and it would be impossible to beat randomly selecting a model ("random") since all models produce the same prediction.

Moreover, theoretically mb_naïve is known to be biased towards more deterministic models (Line 222 Left). (This is also why mb_naïve is deceptively good in MF.N when $\sigma=10$.) Having candidate models of varying noise levels poses significant challenges to such simple methods. This also explains your confusion that:

why the baseline mb_naïve has the lowest OPE error in the MF.G setting and the highest in the MF.N setting

This is precisely because models in MF.G have similar levels of stochasticity (so the bias of mb_naïve is not fully exposed), but those in MF.N have different levels of stochasticity.

It is also claimed that this naive baseline performs poorly in high-noise environments (Lines 356-358 Right) but this is simply not the case. It is the best performing for $\sigma$=100.0 in MF.G g=-30, g=-3, MB.G g=-24 and second best in MB.G g=-30.

We agree that the text here is too brief and perhaps misleading. We are mostly referring to the MF.N experiments when $\sigma$ is high.

---

 

Take for example MF.G with g=-51. Most Methods achieve a low OPE, though this might be only due to the environment being so hard to solve with such high gravities, that all policies basically behave equally bad.

We are afraid that the reviewer might be carrying concepts and mindsets for policy optimization (which is standard in empirical RL) into the policy evaluation problem. The performance of target policies generally does not determine the difficulty of policy evaluation. Even if a target policy has poor performance, the OPE algorithm still needs to correctly predict its (low) value so that the user does not deploy it in the real system. There are no reasons to believe that this will be generally easier than evaluating a good policy; for example, if the offline data comes from a good policy, it can be more difficult to evaluate a poor policy than a good one due to lack of coverage.

---

 

it has become standard practice to probe the "performance" with a random policy

Again, this is a practice for policy optimization, and we are doing evaluation. In fact, we did something similar in spirit: all plots show the "random" baseline that randomly picks one of the candidate models to predict the performance of the target policies. This helps rule out the degeneracy that OPE error is low simply because all candidate models predict the correct value.

---

Misc

Providing true performance values in the environment will make it easier...

We did show this in Figure 1 (left). The plot shows the performance of 10 target policies across models in MF.G of different gravity values (x-label is a typo; should have been "gravity").

---

subsets of only 3 $\mathcal{M}$

First, it's not "3 $\mathcal{M}$", but $|\mathcal{M}|=3$. This is due to our limited computational budget. On the other hand, this still results in nontrivial model selection problem, as all methods still suffer nontrivial OPE errors in Figure 4.

We thank the reviewer for the comments.

---

 

The paper presents relevant and interesting bits of information.

In general such a demonstration seems fitting to the presented claims.

We are glad that the reviewer finds new insights in our paper and that they are supported with evidence.

---

 

It analyzes different method for OPE, model-free as well as model-based.

... the reader should learn about a well-working OPE framework

The reviewer misdescribes our work as analyzing different OPE methods. Quite different, we study model selection over OPE, i.e., selecting between different ``base'' OPE methods that either produce Q-functions or dynamics models (Line 80, right column).

 

I am missing an essential reference and discussion about the "current way to do OPE".

As mentioned above, we are working on the model selection problem, which is ``one-level up'' above (albeit closely related to) the OPE problem. Mathematically we treat base OPE problems as "oracles" that produce either Q-functions or dynamics models (Line 80, right column), which covers a wide range of practical OPE methods considered in the literature (see Appendix A for relevant references about OPE and model selection in OPE). This way, we do not need to worry much about how OPE is done, but focus on selecting from the output of OPE algorithms.

---

 

Do you agree with this point [that "the main selling points... should be... a well-working OPE framework"]?

Again, we do not contribute to OPE itself but study its model selection problem. It is unclear to us whether this confusion has affected the reviewer's understanding of the work, or that the reviewer actually understood the difference (between OPE and model selection over OPE) and was simply not careful when summarizing and describing our work, since the review does not provide further technical comments.

 

This could enable the reader to tackle his OPE task at hand.

It seems that the reviewer feels the paper is like a "practical guide/manual" for OPE. (An example of this would be [VJY21] in our citation.) It is not. Given the under-investigation, we are far from the "practical guide" phase of research; the focus of our work is novel theoretical derivations and comprehensive empirical evaluation of the methods. The "protocol" is not about practical usage, but how we empirically test and understand these algorithms in simulation environments.

---

 

the paper introduces multiple independent claims that are not closely woven together.

We hear you and we are very aware that the paper is unconventional in this aspect when we submit the work. The paper is indeed filled with little bits of new insights here and there. That said, we do think the paper has a clear theme: progress in multiple dimensions on the model selection problem for OPE, which is heavily under-investigated (see Appendix A for relevant works). In particular, we design novel selection algorithms in Sections 3 and 4. Then, naturally one would want to evaluate the algorithms empirically, but existing frameworks/protocols for doing so have many problems, as briefly explained on Line 78, Left Column. So we also propose new protocols that allow more comprehensive empirical understanding of the selection algorithms. We feel these components are naturally connected and valuable to anyone interested in the model selection problem.

We indeed considered the reviewer's implicit suggestion that it might be better to "slice" the work into "multiple papers" ("The motivation for putting those claims together in a single paper instead instead of multiple different papers is not clear.") After careful consideration, we still believe the works is best presented in its current form. For example, one could consider taking out the new selection algorithms and their analyses and publish a purely theoretical paper; however, while the new algorithms take novel insights to come up with, once they come to mind, their theoretical properties naturally follow from existing analyses, so the theoretical contributions alone are likely too thin for a typical conference paper.

---

 

"is unclear""hard to follow"

The review ends several comments with phrases like "unclear" and "hard to follow". Without further concrete comments, it is very difficult for us to understand what is unclear. Perhaps OPE and its model selection does not fit your background and/or it's not a problem that interests you; otherwise, we would like to hear more concrete comments that can help us improve the paper.

---

 

Conclusion

We will add one. The omission was simply due to space limit.

w.p.

This means "with probability", which we spell out in Theorem 1. This is a very standard and widely used abbreviation in ML theory.