Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing
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 estimates. MAPO is applicable to deterministic environments with discrete actions, such as structured prediction and combinatorial optimization. Our key idea is to express the expected return objective as a weighted sum of two terms: an expectation over the high-reward trajectories inside a memory buffer, and a separate expectation over trajectories outside of the buffer. To design an efficient algorithm based on this idea, 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 speed 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 goo.gl/TXBp4e.
This paper describes a Reinforcement Learning algorithm adapted to settings with sparse reward and weak supervision, and applies it to program synthesis, achieving state-of-the-art and even outperforming baselines with full supervision.  The two first sections explain very clearly the motivation of this work, presenting the current limitations of reinforcement learning for tasks like contextual program synthesis. It is nicely written and pleasant to read. Section 3 presents the Reinforcement Learning framework that is the basis of the proposal, where the goal is to find a food approximation of the expected return objective. Section 4 presents the MAPO algorithm and his three key points: "(1) distributed sampling from inside and outside memory with an actor-learner architecture; (2) a marginal likelihood constraint over the memory to accelerate training; (3) systematic exploration to discover new high reward trajectories" (I did not find a better phrasing to summarize than the one in the abstract and the conclusion).  The experiments are carried out on two public datasets, includes details for reproducibility, and show compelling results.  The references are relevant throughout the paper. I cannot attest the completeness, not being an expert in RL. I don't see a reason why this paper should not be accepted!  Some comments:    * Probably a mistake on end of line 152: "smaller stochastic space of size xxx ..." -> "... of measure xxx ...".    * Section 4.1 could be better explained. Why is the enumeration prohibitive? Because of the cost of evaluating new gradients and log probabilities for those trajectories?    * End of section 4.2: "Once the policy is off the ground, almost never the buffer probabilities are truncated given that they are naturally larger than alpha". It would be interesting to see plots of this. no experimental results are given about any properties of these trajectories, but it seems like they would be important to look at to understand the technique. For example, what fraction of the gradient magnitude comes from the buffer and what fraction from the MC samples? Illustrating this would be the cherry on the cake.