Learning to Perform Local Rewriting for Combinatorial Optimization By: Xinyun Chen, Yuandong Tian

[QiXuanWang]

Link: Arxiv

Interestingly, it has no OpenReview comment. Not sure if it's general for NueroIPS or only this one. Yuandong Tian is quite famous in Chinese AI society.

Github: https://github.com/facebookresearch/neural-rewriter

There are some complaints about the quality of the code...

Problem: Another trying with RL on combinatorial optimization problems.

Improving iteratively from an existing solution is a common approach for continuous solution spaces, e.g, trajectory optimization in robotics [34, 47, 31]. However, such methods relying on gradient information to guide the search, is not applicable for discrete solution spaces due to indifferentiablity.

Innovation:

we directly learn a neural-based policy that improves the current solution by iteratively rewriting a local part of it until convergence. Inspired by the problem structures, the policy is factorized into two parts: the region-picking and the rule-picking policy, and is trained end-to-end with reinforcement learning, rewarding cumulative improvement of the solution

Comment: The problem with this paper is it requires an initial workable solution and then apply Actor-Critic style RL to improve it.
As they mentioned:

Our rewriting formulation is especially suitable for problems with the following properties: (1) a feasible solution is easy to find; (2) the search space has well-behaved local structures, which could be utilized to incrementally improve the solution

But I think both are not so easy. So...