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:
- 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.
- 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:
- 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").
- REINFORCE: It applies the REINFORCE estimator within this continuous augmented space.
- Rao-Blackwellization: It analytically integrates out a portion of the random noise to inherently lower the baseline variance.
- 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.
- 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.
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.
Stochastic Categorical Networks
On the MNIST conditional density estimation benchmark, ARSM achieved the lowest test negative log-likelihood, outperforming both biased and unbiased alternatives.
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.
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