Policy Evaluation Using the Ω-Return
We propose the Ω-return as an alternative to the λ-return currently used by the TD(λ) family of algorithms. The benefit of the Ω-return is that it accounts for the correlation of different length returns. Because it is difficult to compute exactly, we suggest one way of approximating the Ω-return. We provide empirical studies that suggest that it is superior to the λ-return and γ-return for a variety of problems.
***After author response/discussion***I have moved my score up for two main reasons: 1) The authors helpful response did clarify the experimental set-up for me, which I agree does not need to include True TD(lambda). I have edited my review below to reflect this.2) I have come around to thinking of the approximate algorithm as a proof of concept rather than a primary contribution. Seeing this paper as describing a solid foothold in this direction, and some early evidence that there may be something to be gained by going further makes me less concerned about its practical impact, and more optimistic about its chances of provoking questions and possibly inspiring follow-on work.---Paper Summary---This paper proposes a novel replacement for the lambda return for mixing between bootstrapping and Monte Carlo estimates in reinforcement learning. Specifically, the Omega return in principle accounts for the covariance of returns at different depths (whereas the lambda return implicitly assumes the returns at various depths are independent). Computation of the Omega return is formulated as a generalized least squares problem, which impractically relies upon unavailable quantities. The paper describes one method for approximating these quantities using experience data. Empirical results in four domains suggest that the approximation produces qualitatively sensible weights, and that the use of the approximate Omega return yields more accurate off-policy estimates of policy quality.---Quality---I believe the derivation of the Omega return weights (the main technical result) is technically sound. The various steps of approximation are generally well-motivated. One argument that I did not totally follow starts on line 208. The argument is intended to motivate the assumption that the covariance between two different depth returns is approximately equal to the variance of the shallower return. Intuitively I can see why this might be reasonable; it seems sensible in many problems to expect the return at one depth to be very similar to a slightly deeper return (less so for much deeper returns, but therein lies the approximation). The thing I didn't get is the argument that the i-step return should be nearly independent of the depth-j TD-error. The claim seems to be that they should be nearly independent because they are *conditionally* independent given state. As I'm sure the authors are aware, there's no reason that two conditionally independent variables should also be independent. If you want to assume those two quantities are independent, it's important to develop a better founded sense of what that assumption really means.The claim that the approximation yields accurate weights is a little imprecise. It is mainly supported by eyeballing the approximated quantities to see that they are qualitatively similar to the targets. I'd have preferred a more quantitative study of the accuracy of the approximation, perhaps studying the relative impact of the various stages of approximation proposed in Section 4.The empirical claim that using the approximate Omega return yields more accurate value estimates than the usual lambda return seems well-supported. ---Clarity---I found the paper to be well-written for the most part. I particularly appreciated the introduction which I thought laid out the issues at hand clearly and effectively set the stage for the technical contributions. The main area for improvement in clarity I see is Section 4. The section takes the reader through multiple different stages of approximation and it starts to feel a bit like a run-on sentence ("and then...and then..."). I'd humbly suggest that the authors take another look at this section with eye toward providing the reader with more structure to hold on to. Some things that might help include additional subheadings, some text along the way to place the current step in the overall approximation plan, and/or perhaps an executive summary at the end of the various assumptions and their consequences.The other major impediment to clarity is the relegation of the description of the experiments to the supplementary material. This make it harder to determine the meaning of the results; the figures even contain terms that are not defined anywhere in the main text. The authors should be aware that they are permitted to place their references section on the 9th page, leaving nearly 3/4 page of available space. While I understand that the appendix as-is cannot fit in that space, I expect that with some judicious editing significantly more detail regarding the experiments can fit in the main text.---Originality---As far as I am aware, the Omega return is a novel concept, and the derivation and subsequent approximation presented here are also original, though they make use of well-known machine learning tools. ---Significance---The conceptual problem with the lambda return is very real, and effectively addressing the bias in the estimator could potentially have an important impact on RL practice. However, this is not a novel insight -- the issues with the lambda return have already been discussed in the literature. So the burden of significance falls to the Omega return itself.The principle underlying the Omega return is a good one, and I wouldn't say that its formulation was a priori obvious. So one source of potential significance (that the paper itself raises) is that the Omega return, as described here, may now serve as a target for approximation for future study.I do see potential value in having this idea available in the literature as a foundation for future work.The other possible source of significance is the particular approximation described here. Unfortunately, to my eyes it looks like this method is fairly complicated and limited compared to the lambda return. As George Box is famous for saying "All models are wrong, but some are useful." Both the approximate Omega return and lambda return are wrong, but from these results I'd be forced to conclude that the lambda return is currently more useful. I doubt the specific approximation method in this paper will significantly impact RL practice. At best it serves as a proof of concept that one can approximate the Omega return to some extent, giving hope that a better approximation will come down the road eventually.