# Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing

arXiv: https://arxiv.org/abs/1807.02322 · HTML: https://mlsanity.com/paper/1807.02322/

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2018.

## Built on by (most cited first, 30 of 57)

- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [TAPEX: Table Pre-training via Learning a Neural SQL Executor](https://mlsanity.com/paper/2107.07653/) (2021)
- [Binding Language Models in Symbolic Languages](https://mlsanity.com/paper/2210.02875/) (2022)
- [FeTaQA: Free-form Table Question Answering](https://mlsanity.com/paper/2104.00369/) (2021)
- [HiTab: A Hierarchical Table Dataset for Question Answering and Natural Language Generation](https://mlsanity.com/paper/2108.06712/) (2021)
- [Large Language Models are few(1)-shot Table Reasoners](https://mlsanity.com/paper/2210.06710/) (2022)
- [TABBIE: Pretrained Representations of Tabular Data](https://mlsanity.com/paper/2105.02584/) (2021)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [Recent Advances in Text-to-SQL: A Survey of What We Have and What We Expect](https://mlsanity.com/paper/2208.10099/) (2022)
- [AIT-QA: Question Answering Dataset over Complex Tables in the Airline Industry](https://mlsanity.com/paper/2106.12944/) (2021)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [A Survey on Table Question Answering: Recent Advances](https://mlsanity.com/paper/2207.05270/) (2022)
- [Neural-Symbolic Solver for Math Word Problems with Auxiliary Tasks](https://mlsanity.com/paper/2107.01431/) (2021)
- [Learning Math Reasoning from Self-Sampled Correct and Partially-Correct Solutions](https://mlsanity.com/paper/2205.14318/) (2022)
- [TacticZero: Learning to Prove Theorems from Scratch with Deep Reinforcement Learning](https://mlsanity.com/paper/2102.09756/) (2021)
- [OmniTab: Pretraining with Natural and Synthetic Data for Few-shot Table-based Question Answering](https://mlsanity.com/paper/2207.03637/) (2022)
- [ReasTAP: Injecting Table Reasoning Skills During Pre-training via Synthetic Reasoning Examples](https://mlsanity.com/paper/2210.12374/) (2022)
- [Large Language Models are Complex Table Parsers](https://mlsanity.com/paper/2312.11521/) (2023)
- [Geographic Question Answering: Challenges, Uniqueness, Classification, and Future Directions](https://mlsanity.com/paper/2105.09392/) (2021)
- [PyGlove: Symbolic Programming for Automated Machine Learning](https://mlsanity.com/paper/2101.08809/) (2021)
- [FORTAP: Using Formulas for Numerical-Reasoning-Aware Table Pretraining](https://mlsanity.com/paper/2109.07323/) (2021)
- [Softened Symbol Grounding for Neuro-symbolic Systems](https://mlsanity.com/paper/2403.00323/) (2024)
- [Improving exploration in policy gradient search: Application to symbolic optimization](https://mlsanity.com/paper/2107.09158/) (2021)
- [From Zero to Hero: Examining the Power of Symbolic Tasks in Instruction Tuning](https://mlsanity.com/paper/2304.07995/) (2023)
- [API-Assisted Code Generation for Question Answering on Varied Table Structures](https://mlsanity.com/paper/2310.14687/) (2023)
- [Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick](https://mlsanity.com/paper/2311.12569/) (2023)
- [On The Ingredients of an Effective Zero-shot Semantic Parser](https://mlsanity.com/paper/2110.08381/) (2021)
- [Neural-Symbolic Recursive Machine for Systematic Generalization](https://mlsanity.com/paper/2210.01603/) (2022)

## Abstract (arXiv)

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