ARSM: Augment-REINFORCE-Swap-Merge Estimator for Gradient Backpropagation Through Categorical Variables

Mingzhang Yin, Yuguang Yue, Mingyuan Zhou

TL;DR

Optimizing machine learning models that use discrete categorical variables is notoriously difficult because you cannot backpropagate gradients through random samples. This paper introduces ARSM (Augment-REINFORCE-Swap-Merge), a novel gradient estimator that is both completely unbiased and exhibits exceptionally low variance. By mapping categorical variables into a continuous space and using a clever "variable swapping" trick, ARSM significantly outperforms existing estimators in training categorical variational autoencoders and reinforcement learning agents.

What Problem Does This Paper Address?

Many important problems in machine learning require optimizing an objective function that depends on discrete categorical choices. Examples include discrete latent variables in deep generative models (like text or discrete autoencoders) and discrete action spaces in reinforcement learning (RL).

The standard tool for training deep networks—gradient backpropagation—relies on functions being smooth and differentiable. Sampling a categorical variable (e.g., picking one of $C$ categories) is a discontinuous step function, which breaks standard backpropagation.

Researchers usually tackle this in one of two ways:

  1. Biased continuous relaxations (like Gumbel-Softmax), which approximate the discrete choices with smooth curves. While computationally efficient, the introduced bias can lead to suboptimal solutions.
  2. Unbiased score-function estimators (like REINFORCE), which are mathematically rigorous but suffer from cripplingly high variance, making training painfully slow or unstable.

While recent advanced estimators have successfully tamed variance for binary variables (where there are only 2 choices), scaling these unbiased, low-variance benefits to categorical variables (where choices $\ge 2$) has remained a major open challenge.

Methods

The authors propose ARSM, which stands for Augment-REINFORCE-Swap-Merge. The estimator achieves low variance without introducing bias through a multi-step mathematical pipeline:

  1. Augmentation: It maps the discrete categorical variable into a continuous space using a symmetric Dirichlet distribution (a technique rooted in the concept of "exponential racing").
  2. REINFORCE: It applies the REINFORCE estimator within this continuous augmented space.
  3. Rao-Blackwellization: It analytically integrates out a portion of the random noise to inherently lower the baseline variance.
  4. Swap (The Key Innovation): By swapping elements of the Dirichlet random vector, the authors construct multiple different but mathematically equivalent representations of the gradient. These swapped vectors act as "pseudo-actions" or alternative paths.
  5. Merge: Finally, it shares common random numbers across these swapped representations to perform a highly effective form of variance reduction (similar to antithetic sampling).

In reinforcement learning, this strategy manifests as a "try-and-see self-critic" approach. Instead of training a separate neural network to act as a baseline "critic" (the standard way to reduce REINFORCE variance), the ARSM agent generates a random number of pseudo-actions at its current state, evaluates their rewards, and uses their average as a dynamic, built-in baseline.

Datasets

The authors evaluated ARSM across several standard benchmarks:

  • Binarized MNIST: Used to evaluate categorical Variational Autoencoders (VAEs)—including both single-layer and hierarchical two-layer architectures—as well as stochastic categorical networks for conditional density estimation.
  • OpenAI Gym Environments: CartPole-v0, Acrobot-v1, and LunarLander-v2 were used to benchmark discrete-action policy optimization in reinforcement learning.

Key Insights and Ideas

  • Symmetry as a Variance Shield: The core "aha moment" of the paper is realizing that swapping elements in a symmetric Dirichlet distribution preserves the distribution itself. This allows the estimator to look at "alternative histories" (pseudo-actions) from a single random sample without changing the underlying math.
  • Self-Tapering Exploration: In reinforcement learning, the number of unique pseudo-actions naturally scales with the agent's uncertainty. Early in training, when the policy is uncertain, ARSM generates many distinct pseudo-actions, providing a rich gradient signal to learn from. As the policy converges and becomes confident, the pseudo-actions collapse to match the true action, naturally driving the gradient variance to zero.
  • Baseline-Free RL: By using the average reward of its own pseudo-actions as a baseline, ARSM completely eliminates the need to construct and tune separate baseline networks, making the optimization process much more robust.

Key Results

Toy Optimization Task

In a univariate setup designed to find an optimal category, ARSM's gradient variance was found to be 1 to 4 orders of magnitude lower than vanilla REINFORCE or advanced baseline methods like RELAX, tracking the true analytical gradient almost perfectly.

Figure 1. Comparison of a variety of gradient estimators in maximizing (13). The optimal solution is σ(φ) = (0, . . . , 1), which means z = C with probability one. The reward is computed analytically by Ez∼Cat(σ(φ))[f(z)] with maximum as 0.533. Rows 1, 2, and 3 show the trace plots of reward E[f(z)], the gradients with respect to φ1 and φC, and the probabilities σ(φ)1 and σ(φ)C, respectively. Row 4 shows the gradient variance estimation with 100 Monte Carlo samples at each iteration, averaged over categories 1 to C.

Categorical VAEs

When training VAEs on binarized MNIST, ARSM achieved a significantly better negative Evidence Lower Bound (ELBO) than its competitors, demonstrating superior generative modeling performance.

Negative ELBO curves on binarized MNIST. ARSM (black line) minimizes the negative ELBO faster and deeper than other methods.

Stochastic Categorical Networks

On the MNIST conditional density estimation benchmark, ARSM achieved the lowest test negative log-likelihood, outperforming both biased and unbiased alternatives.

Table 2 showing test negative log-likelihoods on MNIST conditional density estimation.

Reinforcement Learning

In OpenAI Gym tasks, ARSM demonstrated superior training stability, higher moving average rewards, and significantly lower log-variance compared to standard Advantage Actor-Critic (A2C) and RELAX.

Figure 3. Top row: Moving average reward curves. Bottom row: Log-variance of gradient estimator. In each plot, the solid lines are the median value of ten independent runs (ten different random seeds for random initializations). The opaque bars are 10th and 90th percentiles. Dashed straight lines in Cart Pole and Lunar Lander represent task-completion criteria.

Limitations and Future Work

The primary limitation of ARSM is its computational complexity per step. Because it evaluates the reward function for every unique pseudo-action generated, it can require up to $C$ function evaluations per time step (where $C$ is the number of categories). If the environment simulator or the network's reward function is computationally heavy, this can slow down wall-clock training time.

However, the authors note that these pseudo-action rollouts are entirely independent, meaning they can be computed in an "embarrassingly parallel" manner on modern hardware.

For future work, the authors suggest extending ARSM to high-dimensional discrete action spaces, multi-agent reinforcement learning, and natural language processing tasks like sentence generation and machine translation.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yin2019arsm,
  author = {Mingzhang Yin and Yuguang Yue and Mingyuan Zhou},
  title = {{ARSM: Augment-REINFORCE-Swap-Merge Estimator for Gradient Backpropagation Through Categorical Variables}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
}
Figure