Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing

Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc V. Le, Ni Lao

TL;DR

Memory Augmented Policy Optimization (MAPO) is a reinforcement learning (RL) framework that uses a memory buffer of successful "trajectories" (sequences of actions) to stabilize training and reduce the high variance typically found in policy gradient methods. By splitting the learning objective into samples inside and outside this memory, MAPO achieves state-of-the-art results in program synthesis tasks, even when the model only receives "weak" supervision (knowing the final answer but not the code that produced it).

What Problem Does This Paper Address?

Teaching a computer to write code from natural language—a task known as program synthesis—is notoriously difficult for AI. Most researchers use Reinforcement Learning (RL), where a model tries different code snippets and gets a "reward" if the code produces the correct answer.

However, this approach faces three major hurdles:

  1. Sparse Rewards: In a massive search space of possible programs, almost every random attempt fails. The model gets a reward of zero 99.9% of the time, making it hard to learn anything.
  2. High Variance: When the model finally finds a "gold" program, the gradient update can be so massive or inconsistent that it destabilizes the whole training process.
  3. The "Cold Start" Problem: At the beginning of training, the model is so bad that it never finds a successful program, essentially wandering in the dark forever.

Methods

The authors introduce Memory Augmented Policy Optimization (MAPO) to tackle these challenges. The core innovation is how they handle the "Expected Return" objective. Instead of just sampling randomly, they mathematically split the objective into two parts:

Comparison of MAPO and standard Importance Sampling architectures
  • Inside the Buffer: An expectation over high-reward trajectories already discovered and stored in a memory buffer.
  • Outside the Buffer: An expectation over everything else.

To make this work efficiently in practice, they introduce three key techniques:

  • Memory Weight Clipping: To solve the "cold start," they force the model to pay a minimum amount of attention to the successful programs in the buffer, even if the model's current probability for them is near zero.
  • Systematic Exploration: Using a Bloom filter, the model keeps track of every program it has already tried. This prevents the "actor" from wasting computation on the same failing programs over and over.
  • Distributed Sampling: They use an actor-learner architecture where 30 "actors" explore the space and feed successful samples into a queue for a single "learner" to process, resulting in a 20x speedup.

Datasets

The researchers evaluated MAPO on two major semantic parsing benchmarks:

  • WIKITABLEQUESTIONS (WTQ): A complex dataset where the model must answer questions about Wikipedia tables by generating Lisp-like programs. It involves multi-step reasoning (e.g., "Which country won the most gold medals?").
  • WIKISQL: A large-scale dataset for generating SQL queries from natural language.

Crucially, they focused on weak supervision, meaning the model was never shown the "correct" SQL or Lisp code; it only knew if its generated code produced the right answer for the given table.

Key Insights and Ideas

  • Stratified Sampling for RL: By treating the memory buffer and the "rest of the world" as two separate strata, MAPO provides a lower-variance, unbiased estimate of the gradient. This is much more stable than standard REINFORCE.
  • Don't Forget the "Gold": In standard RL, if a model finds a correct program but then explores away from it, it might "forget" that success. MAPO’s buffer ensures that once a high-reward path is found, it stays in the training loop.
  • The Spurious Program Trap: A major insight was that simply maximizing the likelihood of successful programs (like Maximum Marginal Likelihood does) can be dangerous. A model might find a "spurious" program—code that gets the right answer for the wrong reason (e.g., 2+2 instead of 2*2). MAPO’s RL-based objective is more robust against these "lucky" mistakes than traditional supervised approaches.

Key Results

MAPO demonstrates significant improvements in both sample efficiency and final accuracy compared to strong baselines.

Learning curves on WikiTable and WikiSQL showing MAPO outperforming baselines
  • New State-of-the-Art: On WIKITABLEQUESTIONS, MAPO achieved 46.3% accuracy, a 2.6% improvement over the previous best model.
  • Weak Beats Strong: On WIKISQL, MAPO reached 74.9% accuracy using only weak supervision. This actually outperformed several high-profile models that were trained with full supervision (access to the ground-truth code).
  • Efficiency: The distributed architecture allowed the model to explore billions of sequences while maintaining a manageable training time.

Limitations and Future Work

The authors acknowledge that spurious programs remain a thorn in the side of program synthesis. While MAPO is better at handling them than some baselines, the model can still be biased by programs that yield the correct answer through faulty logic.

Future work could involve integrating MAPO with more advanced "macro-grammars" or holistic triggering mechanisms to further narrow the search space and improve the quality of the generated code. Additionally, the authors suggest that while they focused on deterministic environments, the theoretical framework could potentially be adapted for more stochastic RL settings.

Summary updated

Abstract

We present Memory Augmented Policy Optimization (MAPO), a simple and novel way to leverage a memory buffer of promising trajectories to reduce the variance of policy gradient estimate. MAPO is applicable to deterministic environments with discrete actions, such as structured prediction and combinatorial optimization tasks. We express the expected return objective as a weighted sum of two terms: an expectation over the high-reward trajectories inside the memory buffer, and a separate expectation over trajectories outside the buffer. To make an efficient algorithm of MAPO, we propose: (1) memory weight clipping to accelerate and stabilize training; (2) systematic exploration to discover high-reward trajectories; (3) distributed sampling from inside and outside of the memory buffer to scale up training. MAPO improves the sample efficiency and robustness of policy gradient, especially on tasks with sparse rewards. We evaluate MAPO on weakly supervised program synthesis from natural language (semantic parsing). On the WikiTableQuestions benchmark, we improve the state-of-the-art by 2.6%, achieving an accuracy of 46.3%. On the WikiSQL benchmark, MAPO achieves an accuracy of 74.9% with only weak supervision, outperforming several strong baselines with full supervision. Our source code is available at https://goo.gl/TXBp4e
BibTeX
@inproceedings{liang2018memory,
  author = {Chen Liang and Mohammad Norouzi and Jonathan Berant and Quoc V. Le and Ni Lao},
  title = {{Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=Hk-fGK-dWB},
}
Figure