Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
We consider off-policy estimation of the expected reward of a target policy using samples collected by a different behavior policy. Importance sampling (IS) has been a key technique for deriving (nearly) unbiased estimators, but is known to suffer from an excessively high variance in long-horizon problems. In the extreme case of infinite-horizon problems, the variance of an IS-based estimator may even be unbounded. In this paper, we propose a new off-policy estimator that applies IS directly on the stationary state-visitation distributions to avoid the exploding variance faced by existing methods. Our key contribution is a novel approach to estimating the density ratio of two stationary state distributions, with trajectories sampled from only the behavior distribution. We develop a mini-max loss function for the estimation problem, and derive a closed-form solution for the case of RKHS. We support our method with both theoretical and empirical analyses.
This paper introduces off-policy techniques for estimating average rewards. The technique relies on the fact that average reward has a reformulation based on stationary state distribution. Therefore, instead of computing the importance sampling ratio of the trajectory, which has exponentially exploding variance with the horizon, it suffices to compute the importance sampling ratio of the stationary state distribution. Theoretical and empirical results support the technique.  I find the work quite interesting. The paper is well written. The work is original with a significant contribution, that is, avoiding multiplicative ratios in one case of multi-step off-policy learning. There are some limitations which might be corrected without drastic changes. On the other hand, the scope of the work is more limited than it appeared initially. Authors' response to these concerns will be highly appreciated and useful.  The scope of the technique proposed seems to be limited only to the case of average reward. Much of the work in off-policy learning revolves around what the authors referred to as value-function learning. If this limitation is not clarified up front, the work may leave an impression that it offers to break the curse of the horizon for value-function learning. However, it does not. How this technique applies to value-function learning is not clear. On the other hand, the reformulation of average reward based on stationary state distribution is a known result. In that sense, the overall estimator based on density ratio is quite obvious. Hence, more of the contribution goes here in the particular way the density ratio is estimated here. However, for that, an analysis of computational complexity and providing a pseudo code of the overall technique would have been useful.  Can the authors offer some insight into how value-function learning can benefit from this technique? Alternatively, can you shed some light on the possibility of replacing off-policy value-function learning with off-policy average-reward learning altogether?  *** After author rebuttal ***  Thanks for the clarification that you indeed noted that the paper is about the average reward case. I am not sure the title, which is more general than the contribution, is doing justice to the work. On the other hand, if the extension to the value function learning case is that straightforward, it would have made more sense to start with that first. If the extension is not really that straightforward, it is okay to mention that, which would give more credence to why it was not tried first.  For computational complexity, it would also be useful to know what would be the cost for getting w(s) through (11) in the first place.  Thanks for the rebuttal and well done!