2019

Credit Assignment Techniques in Stochastic Computation Graphs

Weber, Théophane, Heess, Nicolas, Buesing, Lars et al.

Understand

Stochastic computation graphs (SCGs) provide a formalism to represent structured optimization problems arising in artificial intelligence, including supervised, unsupervised, and reinforcement learning.

Previous work has shown that an unbiased estimator of the gradient of the expected loss of SCGs can be derived from a single principle.
However, this estimator often has high variance and requires a full model evaluation per data point, making this algorithm costly in large graphs.
In this work, we address these problems by generalizing concepts from the reinforcement learning literature.

Built on

Applications of advances in nonlinear sensitivity analysis
Werbos, Paul J · 1982
Earlier work this paper cites.
A stochastic approximation method
Robbins, Herbert and Monro, Sutton · 1985
Earlier work this paper cites.
Learning internal representations by error propagation
Rumelhart, David E, Hinton, Geoffrey E, and Williams, Ronald J · 1985
Earlier work this paper cites.
Identifying independence in bayesian networks
Geiger, Dan, Verma, Thomas, and Pearl, Judea · 1990
Earlier work this paper cites.
Gradient estimation via perturbation analysis
Glasserman, Paul · 1991
Earlier work this paper cites.
Smoothing complements and randomized score functions
Glasserman, Paul · 1992
Earlier work this paper cites.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
Williams, Ronald J · 1992
Earlier work this paper cites.
Policy invariance under reward transformations: Theory and application to reward shaping
Ng, Andrew Y, Harada, Daishi, and Russell, Stuart · 1999
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, Richard S, McAllester, David A, Singh, Satinder P, and Mansour, Yishay · 2000
Earlier work this paper cites.
Variance reduction techniques for gradient estimates in reinforcement learning
Greensmith, Evan, Bartlett, Peter L, and Baxter, Jonathan · 2004
Earlier work this paper cites.
Policy gradient critics
Wierstra, Daan and Schmidhuber, Jürgen · 2007
Earlier work this paper cites.
Optimal jacobian accumulation is np-complete
Naumann, Uwe · 2008
Earlier work this paper cites.
Probabilistic graphical models: principles and techniques
Koller, Daphne and Friedman, Nir · 2009
Earlier work this paper cites.
Convergence rates of inexact proximal-gradient methods for convex optimization
Schmidt, Mark, Roux, Nicolas L, and Bach, Francis R · 2011
Earlier work this paper cites.
Value-gradient learning
Fairbank, Michael and Alonso, Eduardo · 2012
Earlier work this paper cites.
Variational bayesian inference with stochastic search
Original
Paisley, John, Blei, David, and Jordan, Michael · 2012
Earlier work this paper cites.
Estimating or propagating gradients through stochastic neurons for conditional computation
Original
Bengio, Yoshua, Léonard, Nicholas, and Courville, Aaron · 2013
Earlier work this paper cites.
Auto-encoding variational Bayes
Original
Kingma, Diederik P and Welling, Max · 2013
Earlier work this paper cites.
Black box variational inference
Original
Ranganath, Rajesh, Gerrish, Sean, and Blei, David M · 2013
Earlier work this paper cites.
Automated variational inference in probabilistic programming
Original
Wingate, David and Weber, Theophane · 2013
Earlier work this paper cites.
Learning stochastic recurrent networks
Original
Bayer, Justin and Osendorfer, Christian · 2014
Earlier work this paper cites.
Value-gradient learning
Fairbank, Michael · 2014
Earlier work this paper cites.
Amortized inference in probabilistic reasoning
Gershman, Samuel and Goodman, Noah · 2014
Earlier work this paper cites.
Efficient gradient-based inference through transformations between bayes nets and neural nets
Original
Kingma, Diederik P and Welling, Max · 2014
Earlier work this paper cites.

Similar

Gps-abc: Gaussian process surrogate approximate bayesian computation
Original
Meeds, Edward and Welling, Max · 2014
Cited alongside, same era.
Neural variational inference and learning in belief networks
Original
Mnih, Andriy and Gregor, Karol · 2014
Cited alongside, same era.
Stochastic backpropagation and approximate inference in deep generative models
Original
Rezende, Danilo Jimenez, Mohamed, Shakir, and Wierstra, Daan · 2014
Cited alongside, same era.
Deterministic policy gradient algorithms
Silver, David, Lever, Guy, Heess, Nicolas, Degris, Thomas, Wierstra, Daan, and Riedmiller, Martin · 2014
Cited alongside, same era.
Black box variational inference for state space models
Original
Archer, Evan, Park, Il Memming, Buesing, Lars, Cunningham, John, and Paninski, Liam · 2015
Cited alongside, same era.
Weight uncertainty in neural networks
Original
Blundell, Charles, Cornebise, Julien, Kavukcuoglu, Koray, and Wierstra, Daan · 2015
Cited alongside, same era.
A recurrent latent variable model for sequential data
Chung, Junyoung, Kastner, Kyle, Dinh, Laurent, Goel, Kratarth, Courville, Aaron C, and Bengio, Yoshua · 2015
Cited alongside, same era.
Deep temporal sigmoid belief networks for sequence modeling
Gan, Zhe, Li, Chunyuan, Henao, Ricardo, Carlson, David E, and Carin, Lawrence · 2015
Cited alongside, same era.
Muprop: Unbiased backpropagation for stochastic neural networks
Original
Gu, Shixiang, Levine, Sergey, Sutskever, Ilya, and Mnih, Andriy · 2015
Cited alongside, same era.
Learning continuous control policies by stochastic value gradients
Heess, Nicolas, Wayne, Gregory, Silver, David, Lillicrap, Tim, Erez, Tom, and Tassa, Yuval · 2015
Cited alongside, same era.
Deep Kalman filters
Original
Krishnan, Rahul G, Shalit, Uri, and Sontag, David · 2015
Cited alongside, same era.
Continuous control with deep reinforcement learning
Original
Lillicrap, Timothy P, Hunt, Jonathan J, Pritzel, Alexander, Heess, Nicolas, Erez, Tom, Tassa, Yuval, Silver, David, and Wierstra, Daan · 2015
Cited alongside, same era.

Then

Noisy networks for exploration
Original
Fortunato, Meire, Azar, Mohammad Gheshlaghi, Piot, Bilal, Menick, Jacob, Osband, Ian, Graves, Alex, Mnih, Vlad, Munos, Remi, Hassabis, Demis, Pietquin, Olivier, et al · 2017
Later among the works it cites.
Backpropagation through the void: Optimizing control variates for black-box gradient estimation
Original
Grathwohl, Will, Choi, Dami, Wu, Yuhuai, Roeder, Geoff, and Duvenaud, David · 2017
Later among the works it cites.
Controlled sequential monte carlo
Original
Heng, Jeremy, Bishop, Adrian N, Deligiannidis, George, and Doucet, Arnaud · 2017
Later among the works it cites.
Efficient structured inference for stochastic recurrent neural networks
Liu, Hao, He, Lirong, Bai, Haoli, and Xu, Zenglin · 2017
Later among the works it cites.
Multi-agent actor-critic for mixed cooperative-competitive environments
Lowe, Ryan, Wu, Yi, Tamar, Aviv, Harb, Jean, Abbeel, Pieter, and Mordatch, Igor · 2017
Later among the works it cites.
Sim-to-real transfer of robotic control with dynamics randomization
Original
Peng, Xue Bin, Andrychowicz, Marcin, Zaremba, Wojciech, and Abbeel, Pieter · 2017
Later among the works it cites.
Parameter space noise for exploration
Original
Plappert, Matthias, Houthooft, Rein, Dhariwal, Prafulla, Sidor, Szymon, Chen, Richard Y, Chen, Xi, Asfour, Tamim, Abbeel, Pieter, and Andrychowicz, Marcin · 2017
Later among the works it cites.
Rebar: Low-variance, unbiased gradient estimates for discrete latent variable models
Tucker, George, Mnih, Andriy, Maddison, Chris J, Lawson, John, and Sohl-Dickstein, Jascha · 2017
Later among the works it cites.
Rudder: Return decomposition for delayed rewards
Original
Arjona-Medina, Jose A, Gillhofer, Michael, Widrich, Michael, Unterthiner, Thomas, and Hochreiter, Sepp · 2018
Later among the works it cites.
Learning and querying fast generative models for reinforcement learning
Original
Buesing, Lars, Weber, Theophane, Racaniere, Sebastien, Eslami, SM, Rezende, Danilo, Reichert, David P, Viola, Fabio, Besse, Frederic, Gregor, Karol, Hassabis, Demis, et al · 2018
Later among the works it cites.
Implicit reparameterization gradients
Original
Figurnov, Michael, Mohamed, Shakir, and Mnih, Andriy · 2018
Later among the works it cites.
Temporal difference variational auto-encoder
Original
Gregor, Karol, Papamakarios, George, Besse, Frederic, Buesing, Lars, and Weber, Theophane · 2018
Later among the works it cites.
Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor
Original
Haarnoja, Tuomas, Zhou, Aurick, Abbeel, Pieter, and Levine, Sergey · 2018
Later among the works it cites.
Deep variational reinforcement learning for POMDPs
Original
Igl, Maximilian, Zintgraf, Luisa, Le, Tuan Anh, Wood, Frank, and Whiteson, Shimon · 2018
Later among the works it cites.
Sequential attend, infer, repeat: Generative modelling of moving objects
Original
Kosiorek, Adam R, Kim, Hyunjik, Posner, Ingmar, and Teh, Yee Whye · 2018
Later among the works it cites.
Reinforcement learning and control as probabilistic inference: Tutorial and review
Original
Levine, Sergey · 2018
Later among the works it cites.
Neural belief states for partially observed domains
Moreno, Pol, Humplik, Jan, Papamakarios, George, Avila Pires, Bernardo, Buesing, Lars, Heess, Nicolas, and Weber, Theophane · 2018
Later among the works it cites.
Variational bayes with synthetic likelihood
Ong, Victor MH, Nott, David J, Tran, Minh-Ngoc, Sisson, Scott A, and Drovandi, Christopher C · 2018
Later among the works it cites.
Total stochastic gradient algorithms and applications in reinforcement learning
Parmas, Paavo · 2018
Later among the works it cites.
The mirage of action-dependent baselines in reinforcement learning
Original
Tucker, George, Bhupatiraju, Surya, Gu, Shixiang, Turner, Richard E, Ghahramani, Zoubin, and Levine, Sergey · 2018
Later among the works it cites.
Variance reduction for policy gradient with action-dependent factorized baselines
Original
Wu, Cathy, Rajeswaran, Aravind, Duan, Yan, Kumar, Vikash, Bayen, Alexandre M., Kakade, Sham, Mordatch, Igor, and Abbeel, Pieter · 2018
Later among the works it cites.
Backprop-q: Generalized backpropagation for stochastic computation graphs
Original
Xu, Xiaoran, Zu, Songpeng, and Zhou, Hanning · 2018
Later among the works it cites.
Probabilistic planning with sequential monte carlo methods
Piché, Alexandre, Thomas, Valentin, Ibrahim, Cyril, Bengio, Yoshua, and Pal, Chris · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…