  To address the challenge of backpropagating the gradient through categorical
variables, we propose the augment-REINFORCE-swap-merge (ARSM) gradient
estimator that is unbiased and has low variance. ARSM first uses variable
augmentation, REINFORCE, and Rao-Blackwellization to re-express the gradient as
an expectation under the Dirichlet distribution, then uses variable swapping to
construct differently expressed but equivalent expectations, and finally shares
common random numbers between these expectations to achieve significant
variance reduction. Experimental results show ARSM closely resembles the
performance of the true gradient for optimization in univariate settings;
outperforms existing estimators by a large margin when applied to categorical
variational auto-encoders; and provides a "try-and-see self-critic" variance
reduction method for discrete-action policy gradient, which removes the need of
estimating baselines by generating a random number of pseudo actions and
estimating their action-value functions.
