weakness of this paper is that the results are asymptotic (i.e., only holds when the number of samples approaches infinite). It is unclear how realistic are the phenomena described in this paper. For example, the convergence rate in Theorem 6 depends polynomially on the term 1/c_\mu, which is the minimum data density over all state-action pairs. For MDPs with large state/action space, the term could be much larger than the number of samples. In other words, it’s unclear whether the dominating term is still characterized by Eq. (6) in real-world OPE tasks.
In addition, this paper doesn’t directly tackle the difficulty of linear OPE tasks. On the one hand, the assumptions such as 1/c_\mu-dependence or upper bound of |F^#_\gamma|_2 exclude some natural hard instances. Are these assumptions an artifact of the analysis, or necessary for the result? On the other hand, the sample complexity of tile-coding estimators is exponential in the dimension d, which is not very realistic.
Minor issues which may cause unnecessary confusion: - The notation f* in Definition 8 and 9 is used to denote different functions. - Does Definition 3 depend on the policy \pi being evaluated (because the term (P\phi)(s,a) depends on \pi)?
- Does Definition 3 depend on the policy \pi being evaluated (because the term (P\phi)(s,a) depends on \pi)?