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

Mingzhang Yin, Yuguang Yue, Mingyuan Zhou

TL;DR

This paper introduces ARSM, a novel gradient estimator for categorical variables that is both unbiased and low-variance. By combining variable augmentation, REINFORCE, and a clever "swap-merge" strategy, ARSM significantly improves optimization performance in tasks involving discrete choices, outperforming existing methods in variational auto-encoders and reinforcement learning.

What Problem Does This Paper Address?

Backpropagating gradients through discrete choices (categorical variables) is a fundamental challenge in machine learning. Standard methods like REINFORCE suffer from high variance, making training unstable and slow. While some techniques exist for binary choices, extending these to multi-way categorical variables (e.g., choosing from 100 different actions) is significantly harder. This paper tackles the problem of efficiently and accurately estimating gradients for these complex categorical distributions, which are prevalent in areas like latent variable models and reinforcement learning with discrete action spaces.

Methods

The core of ARSM lies in a multi-stage process:

  1. Augmentation: The categorical variable is re-expressed using augmented exponential random variables. This allows for a more tractable representation of the gradient.
  2. REINFORCE and Rao-Blackwellization: Standard REINFORCE is applied in this augmented space, and Rao-Blackwellization is used to reduce variance by conditioning on the augmented variables. This results in the AR (Augment-REINFORCE) estimator, which is unbiased but can still have high variance.
  3. Swap-Merge: This is the key innovation. The AR estimator's gradient is expressed in multiple, equivalent ways by "swapping" reference categories. By sharing random numbers across these different but equivalent gradient expressions (the "merge" step), ARSM achieves significant variance reduction. This swap-merge strategy is crucial for handling multi-way categorical variables where simple antithetic sampling (used for binary cases) is insufficient.

Datasets

The paper evaluates ARSM on:

  • Synthetic toy data: Used to illustrate the core mechanism of ARSM.
  • Binarized MNIST dataset: For evaluating categorical variational auto-encoders (VAEs) with one and two categorical hidden layers.
  • Standard RL environments: CartPole, Acrobot, and Lunar Lander from OpenAI Gym, for policy optimization tasks.
  • MNIST conditional distribution estimation benchmark: A standard task for evaluating stochastic networks.

Key Insights and Ideas

  • "Exponential Racing" for Categorical Variables: The paper leverages a property of exponential distributions where the minimum of several independent exponentials corresponds to a categorical choice. This provides a novel way to represent categorical variables and their gradients.
  • The Power of "Swap-Merge": The core idea of creating multiple equivalent gradient expressions by swapping reference categories and then merging them by sharing random numbers is a powerful technique for variance reduction in complex categorical settings.
  • "Try-and-See Self-Critic" for RL: ARSM's application in RL can be intuitively understood as a "try-and-see self-critic" method. It compares the reward of the chosen action with rewards from "pseudo-actions" (generated via the swap-merge mechanism) to guide the policy update, eliminating the need for explicit baseline estimation.
  • Scalability to High Dimensions: ARSM is shown to be computationally efficient even for very large numbers of categories (C) or dimensions (K), making it practical for real-world applications.

Key Results

  • Toy Data: ARSM closely matches the true gradient's performance, outperforming other estimators.
  • Categorical VAEs: ARSM significantly outperforms existing methods (REINFORCE, Gumbel-Softmax, RELAX) in terms of both training and testing ELBOs, achieving lower negative ELBOs. For instance, ARSM achieved ELBOs of 82.0 and 86.7 compared to Gumbel-Softmax's 93.6 and 95.9 on a single-layer VAE.
  • Reinforcement Learning: ARSM demonstrates superior performance across CartPole, Acrobot, and Lunar Lander tasks, showing better stability, higher moving average rewards, and significantly lower gradient variance compared to RELAX and A2C.
  • Stochastic Networks: ARSM achieves the lowest test negative log-likelihood on the MNIST conditional distribution estimation benchmark, outperforming biased and unbiased estimators.
  • Variance Reduction: ARSM consistently exhibits gradient variances that are one to four magnitudes lower than competing methods.

Limitations and Future Work

  • Computational Complexity: While ARSM is efficient, the paper notes that a naive implementation of the swap step can be computationally intensive. However, they state it can be optimized to be scalable.
  • Theoretical Analysis: For C > 2, theoretical analysis of ARS and ARSM becomes challenging, particularly regarding properties like "anti-symmetry." The paper focuses on empirical evaluation for these cases.
  • Future Work: The authors suggest extending ARSM to reinforcement learning with high-dimensional discrete-action spaces, multiple discrete-action agents, and applications in natural language processing tasks like sentence generation and machine translation. They also mention adapting off-the-shelf action-value function estimation methods to further accelerate estimation or reduce variance in RL.

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