For problem solving, making reactive decisions based on problem description is fast but inaccurate, while search-based planning using heuristics gives better solutions but could be exponentially slow. In this paper, we propose a new approach that improves an existing solution by iteratively picking and rewriting its local components until convergence. The rewriting policy employs a neural network trained with reinforcement learning. We evaluate our approach in two domains: job scheduling and expression simplification. Compared to common effective heuristics, baseline deep models and search algorithms, our approach efficiently gives solutions with higher quality.
Summary:
Search-based policies are stronger than a reactive policies, but the resulting time consumption can be exponential. Existing solutions include designing a plan from scratch given a complete problem specification or performing iterative rewriting of the plan, though the latter approach has only been explored in problems where the action and state spaces are continuous.
In this work, the authors propose a novel study into the application of iterative rewriting planning schemes in discrete spaces and evaluate their approach on two tasks: job scheduling and expression simplification. They formulate the rewriting task as a reinforcement learning problem where the action space is the application of a set of possible rewriting rules to modify the discrete state. 
The approach is broken down into two steps. In the first step, a particular partition of the discrete state space is selected as needing to be changed by a score predictor. Following this step, a rule selector chooses which action to perform to modify this state space accordingly.
In the job scheduling task, the partition of the state space corresponds to a single job who’s scheduled time must be changed. the application of a rule to rewrite the state involves switching the order of any two jobs to be run. In the expression simplification task, a state to be rewritten corresponds to a subtree in the expression parse tree that can be converted to another expression.
To train, the authors define a mixed loss with two component:
1. A mean squared error term for training the score predictor that minimizes the difference between the benefit of the executed action and the predicted score given to that node
2. An advantage actor critic method for training the rule selector that uses the difference between the benefit of the executed action and the predicted score given to that node as a reward to evaluate the action sampled from the rule set
Pros:
-The approach seems to be relatively novel and the authors address an important problem.
-The authors don’t make their approach more complicated than it needs to be
Cons:
Notation: The notation could be a lot clearer. The variable names used in the tasks should be directly mapped to those defined in the theory in Section 2. It wasn’t clear that the state s_t in the job scheduling problem was defined as the set of all nodes g_j and their edges and that the {\hat g_t} corresponds to a single node. Also, there are some key details that have been relegated to the appendix that should be in the main body of the paper (e.g., how inference was performed)
Evaluation: The authors perform this evaluation on two automatically generated synthetic datasets. It’s not clear that the method would generalize to real data. Why not try the approach on a task such as grammar error correction? Additionally, I would have liked to see more analysis of the method. Apart from showing the comparison of the method with several baselines, the authors don’t provide many insights into how their method works. How data hungry is the method? Seeing as the data is synthetically generated, how effective would the method be with 10X of the training data, or 10% of it? Were any other loss functions attempted for training the model, or did the authors only try the Advantage Actor Critic? What about a self-critical approach? I'd like to see more analysis of how varying different components of the method such as the rule selector and score predictor affect performance.