Tuan Anh Le

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.
    @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.
    @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.
    @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]