PaperlayerView exact revision on arXiv

Source-linked AI summary

Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing

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

arXiv:1807.02322v5cs.LGcs.AIcs.CLstat.ML

TL;DR

Policy-gradient methods can be unstable and inefficient when rewards are sparse and successful trajectories are hard to discover and retain. MAPO augments policy optimization with a memory of promising trajectories, and improves results on two weakly supervised semantic-parsing benchmarks. The reported WikiTableQuestions and WikiSQL results include gains over prior and fully supervised baselines, respectively.

  • Problem

    Policy-gradient methods can have high-variance estimates, slow cold starts, and unsystematic exploration, making optimization difficult when rewards are sparse and high-reward trajectories are rare.

    Source: §1 · p. 1

  • Method

    MAPO splits expected return between high-reward trajectories in a memory buffer and trajectories outside it, with clipping, systematic exploration, and distributed sampling to improve training efficiency.

    Source: §1 · p. 2

  • Results

    MAPO improves both benchmarks: WikiTableQuestions accuracy is 46.3%, 2.6% above the previous state of the art, while weakly supervised WikiSQL outperforms several fully supervised baselines.

    Source: §1 · p. 2, §5.3 · p. 8, §7 · p. 9

  • Takeaways & Limitations

    MAPO provides an RL-based approach to semantic parsing that can outperform fully supervised baselines on WikiSQL without gold programs.

    Source: §2 · p. 2, §7 · p. 9

    High-reward trajectories in memory can be spurious, and maximizing their likelihood can bias training gradients.

    Source: §4 · p. 4

Abstract

from arXiv · show

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

1 Introduction

Policy-gradient learning can be unstable and sample-inefficient, especially when rewards are sparse and high-reward trajectories are easily forgotten. MAPO uses a memory of promising trajectories and reports gains on two semantic-parsing benchmarks.

1 Introduction

  • Policy gradients can be unstable and sample-inefficient; in sparse-reward tasks, long action sequences make high rewards rare and policy sampling can forget successful trajectories.This is especially challenging in large search spaces such as program synthesis and robotics.Source: §1 · p. 1
  • MAPO divides expected return between promising trajectories in memory and trajectories outside it, yielding unbiased, lower-variance gradient estimates while retaining high-reward trajectories.Memory weight clipping, systematic exploration, and distributed sampling are proposed to accelerate and stabilize training, find high-reward trajectories, and scale sampling.Source: §1 · p. 2
  • 46.3% test accuracy on WikiTableQuestions, 2.6% above the previous state of the art, and 74.9% accuracy on WikiSQL with weak supervision, outperforming strong fully supervised baselines.The previous WikiTableQuestions state of the art was 43.7%.Source: §1 · p. 2

2 The Problem of Weakly Supervised Contextual Program Synthesis

Weakly supervised contextual program synthesis maps questions or textual descriptions to programs without gold action sequences. The task requires discovering programs that yield correct answers and generalizing to new contexts.

2 The Problem of Weakly Supervised Contextual Program Synthesis

  • Contextual program synthesis maps a natural-language question to a structured query, or a textual problem description to source code, without gold action sequences in the weakly supervised setting.The model must discover programs that produce the correct answer in context and generalize to new contexts.Source: §2 · p. 2
  • A program is scored by its reward given the context and correct answer; one example is a binary reward for whether execution returns the correct answer.The context includes the input and an environment, such as an interpreter or database, in which the program executes.Source: §2 · p. 2
  • Contextual program synthesis is framed as reinforcement learning with sparse terminal rewards and deterministic transitions, where generalization to new contexts is central.The stated objective is maximum empirical return on a held-out test set.Source: §2 · p. 2

3 Optimization of Expected Return via Policy Gradients

The section formulates program generation as optimizing expected reward under a conditional policy. It describes Monte Carlo policy-gradient estimation and identifies the difficulty of accurate estimates from few fresh samples.

3 Optimization of Expected Return via Policy Gradients

  • Autoregressive models assign program probability token by token, typically using a recurrent neural network to predict each token from the prefix and context.A special end-of-sequence token handles variable program lengths.Source: §3 · p. 3
  • The objective is to optimize expected program reward under a conditional distribution over possible programs given the context.At synthesis time, the most likely program under the learned distribution can be found by exact or approximate inference.Source: §3 · p. 3
  • REINFORCE estimates expected-return gradients from current-policy Monte Carlo trajectories, with a baseline to reduce variance; accurate estimates remain difficult with only a few fresh samples.Entropy may also be added to the objective to discourage early convergence.Source: §3 · p. 3

4 MAPO: Memory Augmented Policy Optimization

MAPO uses a memory of promising trajectories to split expected return optimization into expectations inside and outside the buffer. Clipping, systematic exploration, and distributed sampling make this approach more efficient and stable.

4 MAPO: Memory Augmented Policy Optimization

  • MAPO splits expected return into buffer and outside-buffer expectations, reducing gradient variance through exact or stratified sampling.The setting assumes finite discrete actions, deterministic transitions, and deterministic terminal returns.Source: §4 · pp. 3–4

4.1 Memory Weight Clipping

  • Clipping the memory weight to at least α can accelerate and stabilize early training, though clipping initially biases the gradient estimate.Once the policy assigns memory weight above α naturally, clipping is inactive and gradients are no longer biased by it.Source: §4.1 · pp. 4–5

4.2 Systematic Exploration

  • Systematic exploration excludes already explored partial sequences, avoids wasteful repeated samples, and discovers high-reward trajectories for the buffer.A bloom filter can represent billions of explored sequences using several gigabytes of memory.Source: §4.2 · p. 5

4.3 Distributed Sampling

  • When enumerating a large buffer is costly, sampling approximates its expectation while preserving variance reduction; sampling cost can be distributed across actors.Actors sample inside the buffer through renormalization and outside it through rejection sampling.Source: §4.3 · p. 5
  • 20 times speedup from distributed sampling with 30 actors shows the benefit of distributing sampling across actors.The actor-learner design distributes sampling work while a learner updates parameters from queued samples.Source: §4.3 · p. 5

4.4 Final Algorithm

  • The final algorithm uses asynchronous actors with per-actor buffers to collect inside- and outside-buffer samples for a learner that updates policy parameters.Actors use periodically synchronized stale policies, and samples receive clipped memory-weight or complementary outside-buffer weights.Source: §4.4 · p. 6

5 Experiments

MAPO is evaluated on WikiTableQuestions and WikiSQL, with weakly supervised performance compared against baselines and prior systems. It outperforms the previous state of the art on WikiTableQuestions and several fully supervised WikiSQL systems, while ablations examine systematic exploration and memory weight clipping.

5 Experiments

  • The experiments evaluate semantic parsing on WikiTableQuestions and WikiSQL, using question-answer pairs for weak supervision and table-query programs as the task.WikiTableQuestions has 2,108 tables and 18,496 question-answer pairs; WikiSQL has 24,241 tables and 80,654 question-program pairs, with simpler semantics.Source: §5 · p. 6, §5.1 · p. 6

5.1 Experimental setup

  • The setup uses a neural programmer paired with a symbolic Lisp interpreter; systematic exploration initializes each example’s memory, with distributed sampling used for WikiTableQuestions.WikiSQL memory buffers are truncated to five programs and enumerated; samples outside memory are drawn by rejection sampling.Source: §5.1 · pp. 6–7

5.2 Comparison to baselines

  • Removing systematic exploration or memory weight clipping significantly weakens MAPO, while REINFORCE barely learns because random-policy samples usually receive zero reward.MML and Hard EM converge faster but underperform MAPO; IML runs faster but is prone to spurious programs.Source: §5.2 · pp. 7–8

5.3 Comparison to state-of-the-art

  • On WikiTableQuestions, MAPO outperforms the previous state of the art by 2.6%; on WikiSQL, weakly supervised MAPO outperforms several strong fully supervised baselines.The results are reported in Tables 3 and 4, respectively.Source: §5.3 · p. 8, Table 3 · p. 8, Table 4 · p. 8

5.4 Analysis of Memory Weight Clipping

  • The clipping fraction approaches zero toward the end of training and is negatively correlated with training accuracy; a fixed threshold works, while gradually lowering it can remove clipping bias.Figure 3 tracks clipping fraction and training accuracy over log-scaled training steps.Source: §5.4 · p. 8, Figure 3 · p. 9
  • Table 2 reports mean dev accuracy and standard deviation across five runs for ablations of systematic exploration and memory weight clipping.The accompanying comparison reports that removing either technique significantly weakens MAPO.Source: Table 2 · p. 8, §5.2 · p. 8

6 Related work

Related work frames weakly supervised program synthesis as difficult because it requires searching a large program space through non-differentiable symbolic operations. MAPO is distinguished by reusing high-reward trajectories for variance reduction and using systematic exploration in enumerable, deterministic search spaces.

Program synthesis & semantic parsing

  • Weakly supervised semantic parsing requires searching a large program space through non-differentiable interaction with a symbolic interpreter, where simple policy gradients have shown negative results [17] [34].MAPO focuses on contextualized program synthesis, where generalization to new contexts matters.Source: §6 · p. 9

Experience replay

  • MAPO reuses high-reward trajectories to address sparse rewards, aiming for unbiased, lower-variance gradients rather than fixed trajectory weights that can bias estimates [26].Training equally on same-reward trajectories can be prone to spurious programs.Source: §6 · p. 9

Variance reduction

  • MAPO reformulates gradients as expectations inside and outside memory, reducing variance through smaller-space or stratified sampling and clipping memory weights to accelerate and stabilize training.Unlike approaches relying on supervised pretraining or rewarding samples, MAPO is designed for settings without supervised data.Source: §6 · p. 9

Exploration

  • Because program-synthesis search spaces are enumerable and deterministic, MAPO proposes systematic exploration that ensures only novel trajectories are generated.This contrasts with exploration approaches based on information gain or pseudo-count rewards.Source: §6 · p. 9

7 Conclusion

MAPO combines memory weight clipping, systematic exploration, and distributed sampling from inside and outside the memory buffer. Evaluated on weakly supervised semantic parsing, it outperforms prior state of the art on WikiTableQuestions and several fully supervised baselines on WikiSQL.

7 Conclusion

  • MAPO combines memory weight clipping, systematic exploration, and distributed inside/outside sampling; on WikiTableQuestions it is the first RL approach to significantly outperform prior state of the art, and on WikiSQL weak supervision beats several full-supervision baselines.The techniques are intended to accelerate and stabilize training, discover high-reward trajectories, and scale up training, respectively.Source: §7 · p. 9

A Domain Specific Language

The appendix describes a Lisp-like domain-specific language built from typed functions and gives examples of generated programs. The experiments use the full function set for WikiTableQuestions and a subset for WikiSQL.

A Domain Specific Language

  • Programs are Lisp-like lists of expressions built from functions with typed arguments, return values, and semantics; columns are categorized by whether their cell values are numbers, dates, or strings.Table 5 lists functions used in the experiments.Source: A Domain Specific Language · p. 14, Table 5 · p. 14
  • WikiTableQuestions uses all defined functions, while WikiSQL uses a subset suited to its simpler question semantics.The specified WikiSQL subset includes hop, filter, count, maximum, minimum, average, and sum functions.Source: A Domain Specific Language · p. 14
  • The added same_as function appears in 1.2% of generated programs; removing it would not change the significance of the difference in Table 3.Among programs using same_as, 0.6% are correct and 0.6% incorrect.Source: A Domain Specific Language · p. 14

B Examples of Generated Programs

C Analysis of Sampling from Inside and Outside Memory Buffer

Under binary rewards and exhaustive exploration, the analysis compares sampling with and without a baseline. A baseline gives lower variance when memory-buffer probability is near one and outside-buffer variance is not much larger; otherwise, no baseline is preferable.

C Analysis of Sampling from Inside and Outside Memory Buffer

  • The analysis assumes binary rewards and exhaustive exploration, with memory containing all high-reward samples and the outside set containing all non-rewarded samples.It offers guidance on sample allocation and baseline use; the paper leaves empirical investigation of baselines for future work.Source: C Analysis of Sampling from Inside and… · p. 15

C.1 Variance: baseline vs no baseline

  • Both the baseline and no-baseline estimators reduce gradient-estimation variance, and their variance ratio determines which is preferable.The comparison is based on the ratio of their variances.Source: §C.1 · p. 16
  • A baseline lowers gradient-estimation variance when πθ(B) is near 1.0 and σ− is not much larger than σ+; otherwise, omitting it is preferable.The passage associates πθ(B) near 1.0 roughly with later training.Source: §C.1 · p. 16

C.2 Optimal Sample Allocation

For stratified sampling to estimate the REINFORCE gradient with baseline 2, the optimal allocation assigns equal sample counts to the memory set B and its complement A ´ B. This follows from the allocation rule under the stated similar-variance assumption.

C.2 Optimal Sample Allocation

  • The equal-count result assumes that the gradient of log likelihood has similar variance on B and A ´ B.Source: §C.2 · p. 16
  • Optimal stratified allocation gives more samples to strata with greater probability mass and gradient standard deviation.The sample count for a stratum is proportional to its probability mass times its standard deviation.Source: §C.2 · p. 16
  • The optimal strategy allocates the same number of samples to B and A ´ B.This is the stated result for stratified estimation of the REINFORCE gradient with baseline 2.Source: §C.2 · p. 16

D Distributed Actor-Learner Architecture

The paper describes a distributed actor-learner architecture and reports its compute setup and runtime. For WikiTableQuestions random exploration, pruning rules use sentence triggers but are not applied during training or evaluation.

D Distributed Actor-Learner Architecture

E Pruning Rules for Random Exploration on WikiTableQuestions

  • WikiTableQuestions pruning rules use trigger words or POS tags for selected functions during random exploration only; other functions have no such constraints.The rules are inspired by the grammar and are not applied during training or evaluation; Table 7 presents the rules.Source: E Pruning Rules for Random Exploration… · p. 17, Table 7 · p. 17
Loading 1807.02322v5…