Weighted importance sampling for off-policy learning with linear function approximation
Importance sampling is an essential component of off-policy model-free reinforcement learning algorithms. However, its most effective variant, weighted importance sampling, does not carry over easily to function approximation and, because of this, it is not utilized in existing off-policy learning algorithms. In this paper, we take two steps toward bridging this gap. First, we show that weighted importance sampling can be viewed as a special case of weighting the error of individual training samples, and that this weighting has theoretical and empirical benefits similar to those of weighted importance sampling. Second, we show that these benefits extend to a new weighted-importance-sampling version of offpolicy LSTD( ). We show empirically that our new WIS-LSTD( ) algorithm can result in much more rapid and reliable convergence than conventional off-policy LSTD( ) (Yu 2010, Bertsekas & Yu 2009).
1 Importance sampling and weighted importance sampling Importance sampling (Kahn & Marshall 1953, Rubinstein 1981, Koller & Friedman 2009) is a wellknown Monte Carlo technique for estimating an expectation under one distribution given samples from a different distribution. Consider that data samples Y k 2 R are generated i.i.d. from a sample distribution l, but we are interested in estimating the expected value of these samples, v
, under a different distribution g. In importance sampling this is achieved simply by averaging the samples weighted by the ratio of their likelihoods ⇢
, called the importance-sampling ratio. That is, v g is estimated as:ṽ
This is an unbiased estimate because each of the samples it averages is unbiased:
Unfortunately, this importance sampling estimate is often of unnecessarily high variance. To see how this can happen, consider a case in which the samples Y k are all nearly the same (under both distributions) but the importance-sampling ratios ⇢ k vary greatly from sample to sample. This should be an easy case because the samples are so similar for the two distributions, but importance sampling will average the ⇢ k Y k , which will be of high variance, and thus its estimates will also be of high variance. In fact, without further bounds on the importance-sampling ratios,ṽ g may have infinite variance (Andradóttir et al. 1995, Robert & Casella 2004).
An important variation on importance sampling that often has much lower variance is weighted importance sampling (Rubinstein 1981, Koller & Friedman 2009). The weighted importance sampling (WIS) estimate v g as a weighted average of the samples with importance-sampling ratios as weights:
This estimate is biased, but consistent (asymptotically correct) and typically of much lower variance than the ordinary importance-sampling (OIS) estimate, as acknowledged by many authors (Hesterberg 1988, Casella & Robert 1998, Precup, Sutton & Singh 2000, Shelton 2001, Liu 2001, Koller & Friedman 2009). For example, in the problematic case sketched above (near constant Y k , widely varying ⇢ k ) the variance of the WIS estimate will be related to the variance of Y k . Note also that when the samples are bounded, the WIS estimate has bounded variance, because the estimate itself is bounded by the highest absolute value of Y k , no matter how large the ratios ⇢ k are (Precup, Sutton & Dasgupta 2001).
Although WIS is the more successful importance sampling technique, it has not yet been extended to parametric function approximation. This is problematic for applications to off-policy reinforcement learning, in which function approximation is viewed as essential for large-scale applications to sequential decision problems with large state and action spaces. Here an important subproblem is the approximation of the value function-the expected sum of future discounted rewards as a function of state-for a designated target policy that may differ from that used to select actions. The existing methods for off-policy value-function approximation either use OIS (Maei & Sutton 2010, Yu 2010, Sutton et al. 2014, Geist & Scherrer 2014, Dann et al. 2014 or use WIS but are limited to the tabular or non-parametric case (Precup et al. 2000, Shelton 2001). How to extend WIS to parametric function approximation is important, but far from clear (as noted by Precup et al. 2001).
Summary=============The paper brings the idea of weighted importance sampling (WIS) to off-policy policy evaluation. The core of the work is built around the observation that WIS can be formulated as a weighted regression problem and the corresponding formulation is extended to the problem of linear approximation in off-policy policy evaluation. The soundness of the method is discussed in detail and its empirical effectiveness is evaluated in a simple chain problem.Quality==============The way the paper is written may give the impression that the application of WIS is very simple and almost obvious. Nonetheless, as remarked by the authors, bringing WIS to off-policy evaluation was not trivial and it required a deep understanding of the structure of WIS.The main contributions of the paper are:1- I found the formulation of OIS and WIS in eq. 2 and 3 and their extension to linear regression very simple but elegant and very insightful. Eqs. 5 and 6 clearly reveal how the idea of OIS and WIS estimators smoothly extend to the case of linear regression. This is further supported by the analysis in Section 3. There are only two aspects that I would like the authors to clarify further:a- The definition of the OIS and WIS linear estimators only correct for the unbalance in the output distribution, while the possible difference in the input distributions is not taken into account (starting from the definition of J^{MSE}). Why? How would you correct differences in the input distribution?b- In the analysis in Section 3 no discussion is provided about whether WIS-LS may actually benefit from similar variance-reduction properties as for WIS. It would be helpful to report in sections 1/2 a more clear overview of the theoretical results available for WIS and discuss in section 3 how much these results may extend to the linear regression case.2- The paper then proceeds in extending the WIS-LS idea to the off-policy evaluation problem, notably reformulating the LSTD(lambda) algorithm. Furthermore, a fully online version of the algorithm is provided with constant computational complexity over time. There are two aspects of this part which are not fully clear:a- In Thm.7 it is shown that WIS-LSTD(lambda) reduces to WIS-LS in the Monte-Carlo, finite-horizon case. Given that WIS-LS corrects only for the output distribution (in this case the sum of rewards), I am not sure I fully understand how this is sufficient in the off-policy case, when the state-action distribution (which corresponds to the input distribution) may vary because of the different policies.b- The incremental definition of WIS-LSTD(lambda) still requires the inversion of a matrix of the dimensionality of the number of features (m^3), while usual online implementations of TD only have a linear complexity per step. Do you think such a linear-complexity implementation may be actually possible?3- Finally, the paper reports preliminary empirical results in a simple exact and approximate chain problem. Although the test is very simple, it illustrates the performance of the proposed method along multiple dimensions: number of steps, lambda, and regularizer. Results show a clear advantage of the weight importance sampling solution both in performance and robustness in the parameter selection. The only drawback of this part of the paper is that the problem is really simple and a more extensive empirical evaluation on more challenging problems would definitely benefit to the paper.4- Although the authors reference most of the relevant literature, no discussion and comparison is provided w.r.t. the recent paper:Doubly Robust Policy Evaluation and Learning Authors: John Langford, Lihong Li and Miroslav DudíkConference: Proceedings of the 28th International Conference on Machine Learning (ICML-11)which study a very much related problem. Another very much related paper isHirotaka Hachiya, Takayuki Akiyama, Masashi Sugiyama, Jan Peters: Adaptive importance sampling for value function approximation in off-policy reinforcement learning. Neural Networks 22(10): 1399-1410 (2009)which seems to have an overlap with the current submission.Clarity==============The paper is very well written.Originality==============As reviewed by the authors, the idea of importance sampling has been already applied in off-policy learning in the past. The way the authors bring weighted importance sampling to RL through the clean and elegant formulation of WIS-LS in LSTD is original. Nonetheless, I encourage the authors to have a more thorough discussion with existing literature point out similarities and differences in order to understand better the originality of the contribution. Significance==============Off-policy evaluation is a crucial problem in a huge variety of problems and effective solutions to this problem may have a significant impact.***************************************** AFTER REBUTTALThanks to the authors for their reply. The comparison sketched in the rebuttal is fair and seems convincing. Thus I confirm my positive impression about the paper and I strongly encourage them to revise the paper including the reference and discussion.