Memory Augmented Policy Optimization for Program Synthesis with Generalization

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

Reinforcement Learning (RL) has long promised to revolutionize how we teach machines to write code. However, in program synthesis—where a model must turn natural language into a functional program—rewards are notoriously sparse. If a model generates a thousand lines of code and just one character is wrong, the reward is often zero. This "needle in a haystack" problem makes standard policy gradient methods like REINFORCE unstable and sample-inefficient.

Researchers from Google Brain and Tel-Aviv University introduce Memory Augmented Policy Optimization (MAPO), a novel framework designed to stabilize training and boost performance in deterministic, discrete environments.

The Challenge: Sparse Rewards and Forgetting

The core challenge in weakly supervised program synthesis is the sparse reward problem. When only the final answer (e.g., "Thailand") is available without the intermediate program, the search space is astronomical.

Standard RL agents explore by sampling from their current policy. If they find a "gold" program, they update weights to increase its likelihood. However, if the policy is "cold" (randomly initialized), it might assign such a low probability to that program that the gradient update is negligible. Furthermore, if the agent fails to sample that specific program again soon, it "forgets" the discovery, leading to unstable learning.

The MAPO Framework

MAPO reformulates the standard expected return objective. Instead of a single expectation over all possible trajectories, it splits the search space into two sets: trajectories inside a memory buffer ($B$) and those outside ($A - B$).

Comparison of MAPO and standard Importance Sampling architectures. MAPO explicitly separates samples inside and outside the memory buffer to reduce variance.

1. The MAPO Objective

The objective is a weighted sum: $$\mathcal{O}_{MAPO} = \pi_B \mathbb{E}_{inside} + (1 - \pi_B) \mathbb{E}_{outside}$$ where $\pi_B$ is the total probability the current policy assigns to all trajectories in the buffer. This allows the model to get an exact, low-variance gradient from "known" high-reward samples while still exploring the unknown.

2. Memory Weight Clipping

To solve the "cold start" problem, a clipping mechanism is introduced. If the policy assigns a very low probability to the buffer ($\pi_B < \alpha$), it is forced to $\alpha$. This ensures the model always learns from high-reward trajectories it has already found, preventing it from ignoring them during early training stages.

3. Systematic Exploration

In deterministic environments, sampling the same failed program twice is inefficient. MAPO uses a Bloom filter to track every explored trajectory, ensuring the exploration budget is spent on truly novel paths.

Key Insights: Stratified Sampling

By splitting the search space into "inside memory" and "outside memory," MAPO performs stratified sampling. This statistical technique significantly reduces gradient estimate variance compared to pure Monte Carlo sampling used in standard RL. The authors realized that the failure of REINFORCE isn't just about finding the reward; it's about the policy's inability to "trust" the reward once found. Clipping the memory weight acts as a curriculum, forcing the model to learn from its successes even when it lacks confidence.

Experimental Results

The authors evaluated MAPO on two major semantic parsing benchmarks:

  • WIKITABLEQUESTIONS: A challenging dataset requiring multi-step reasoning over Wikipedia tables. MAPO achieved a new state-of-the-art 46.3% accuracy, a 2.6% improvement over previous best models.
  • WIKISQL: Tested under weak supervision (answer-only), MAPO reached 74.9% accuracy, outperforming several strong baselines that had access to "gold" programs during training.

Ablation studies showed that removing either Systematic Exploration or Memory Weight Clipping caused performance to crater, proving these are core components of the algorithm's success.

Limitations and Future Directions

While successful, MAPO faces challenges with spurious programs—programs that yield the correct answer for the wrong reason. Additionally, MAPO is optimized for deterministic environments with discrete actions. Adapting these variance reduction techniques to stochastic or continuous control environments remains an open research question.

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://github.com/crazydonkey200/neural-symbolic-machines
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 with Generalization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=Hk-fGK-dWB},
}
Figure