REINFORCE trick

07 November 2016

This is a note about a Monte Carlo estimation method under various names: REINFORCE trick (Williams, 1992), score function estimator (Fu, 2006), likelihood-ratio estimator (Glynn, 1990).

Consider a random variable \(X: \Omega \to \mathcal X\) whose distribution is parameterized by \(\phi\); and a function \(f: \mathcal X \to \mathbb R\). The goal is to approximate \(\frac{\partial}{\partial \phi} \E[f(X)]\).

Let \(p_{\phi}(x)\) be the density of \(X\) with respect to the base measure \(\mathrm dx\). Using the identity \(\frac{\partial}{\partial \phi} p_{\phi}(x) = p_{\phi}(x) \frac{\partial}{\partial \phi} \log p_{\phi}(x)\), we get: \begin{align} \frac{\partial}{\partial \phi} \E[f(X)] &= \frac{\partial}{\partial \phi} \int_{\mathcal X} f(x) p_{\phi}(x) \,\mathrm dx \\
&= \int_{\mathcal X} f(x) \frac{\partial}{\partial \phi} p_{\phi}(x) \,\mathrm dx \\
&= \int_{\mathcal X} f(x) \frac{\partial}{\partial \phi} \log p_{\phi}(x) p_{\phi}(x) \,\mathrm dx \\
&= \E\left[f(x) \frac{\partial}{\partial \phi} \log p_{\phi}(x)\right]. \end{align}

Hence, \(\frac{\partial}{\partial \phi} \E[f(X)]\) can be approximated by a Monte Carlo estimator: \begin{align} \frac{1}{N} \sum_{n = 1}^N f(X^n) \frac{\partial}{\partial \phi} \log p_{\phi}(X^n) && X_n \sim p_{\phi}, n = 1, \dotsc, N. \end{align}

Thus, we only need \(\log p_{\phi}(x)\) to be differentiable with respect to \(\phi\). This estimator applicable to a wide range of distributions of \(X\) but suffers from high variance (why?).

---

References

1. Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4), 229–256.
   • Bib

   @article{williams1992simple,
     title = {Simple statistical gradient-following algorithms for connectionist reinforcement learning},
     author = {Williams, Ronald J},
     journal = {Machine learning},
     volume = {8},
     number = {3-4},
     pages = {229--256},
     year = {1992},
     publisher = {Springer}
   }
   

2. Fu, M. C. (2006). Gradient estimation. Handbooks in Operations Research and Management Science, 13, 575–616.
   • Bib

   @article{fu2006gradient,
     title = {Gradient estimation},
     author = {Fu, Michael C},
     journal = {Handbooks in operations research and management science},
     volume = {13},
     pages = {575--616},
     year = {2006},
     publisher = {Elsevier}
   }
   

3. Glynn, P. W. (1990). Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33(10), 75–84.
   • Bib

   @article{glynn1990likelihood,
     title = {Likelihood ratio gradient estimation for stochastic systems},
     author = {Glynn, Peter W},
     journal = {Communications of the ACM},
     volume = {33},
     number = {10},
     pages = {75--84},
     year = {1990},
     publisher = {ACM}
   }
   

[back]