We tackle the challenge of using machine learning to find algorithms with strong worst-case guarantees for online combinatorial optimization problems. Whereas the previous approach along this direction (Kong et al., 2018) relies on significant domain expertise to provide hard distributions over input instances at training, we ask whether this can be accomplished from first principles, i.e., without any human-provided data beyond specifying the objective of the optimization problem. To answer this question, we draw insights from classic results in game theory, analysis of algorithms, and online learning to introduce a novel framework. At the high level, similar to a generative adversarial network (GAN), our framework has two components whose respective goals are to learn the optimal algorithm as well as a set of input instances that captures the essential difficulty of the given optimization problem. The two components are trained against each other and evolved simultaneously. We test our ideas on the ski rental problem and the fractional AdWords problem. For these well-studied problems, our preliminary results demonstrate that the framework is capable of finding algorithms as well as difficult input instances that are consistent with known optimal results. We believe our new framework points to a promising direction which can facilitate the research of algorithm design by leveraging ML to improve the state of the art both in theory and in practice.
Update to the Review after the rebuttal from the Authors:
After carefully reviewing the responses by the authors especially on my concerns about the significance of solving an instance of a given problem and the improvement in the exposition of the ideas I would like to amend my earlier decision and recommend to accept. For completeness below is the original review.
 
This paper introduces a framework to learn to generate solutions to online combinatorial optimization problems with worst case guarantees. The framework as the authors claim eliminates the need for manual hard to solve instance/data creation, which is necessary to teach the model to provide the aforementioned worst case guarantees.  Therefore the main contribution of the paper can be said that this framework shows that it is possible to train a machine learning model, which can learn an algorithm to solve hard online combinatorial optimization problems and this training can be done without knowing much about the actual optimization problem domain. The only input required is the way to calculate the objective function of the actual problem. This contribution is demonstrated on two classes of problems: Ski-Rental and Fractional AdWords. The framework requires two neural networks one for solution generation agent and one for problem instance generation. These two networks are trained jointly from scratch and the underlying algorithm for the training is provided. 
Although a generic framework that learns to solve online combinatorial optimization problems without domain knowledge is by itself a very motivational goal neither the paper successfully demonstrates that the framework the authors propose achieves this goal nor it explains well enough why one would take the machine learning approach to find good algorithms to such problems. Is it because the ML solution would be faster to compute with big instances? Is it because with the proposed approach one can curate sophisticated heuristic solutions when provable optimality is out of reach?
This paper should be rejected because proposed method demonstrates that an instance of one class of problems, Fractional Adwords, can be learned to solve without domain expertise, however fails to prove that the approach would be beneficial for any other instances of the same problem. Although they show that the Ski Rental problem can also be learned to solve though it is trivial and does not even use the framework the authors propose in its full extent, ie. problem instances are not generated by use of a machine learning model, which is one of main claims the authors are making. Therefore I do not find being able to solve this problem as a supporting evidence for the contributions claimed. In particular there is not any theoretical not experimental evidence that the approach would scale to any instances where a pure optimization approach would be slow to provide any meaningful solutions. I find this important because for combinatorial optimization usually scale matters a lot. While a small instance of a problem can be solve by a general purpose solver quickly a small increase in the problem size can turn out to be intractable. When proposing a machine learning approach to such problems I would expect the model to scale better than pure optimization approach so that there would be demonstrable benefit. Although the paper proposes an interesting framework I would argue that it is a “green apple” in the sense that authors need to motivate the approach better and expand the contribution beyond solving a particular instance. Authors acknowledge the fact that their experimental setup is rather limited in Appendix C.1, which I agree with and they also claim that there is a representation for a uniform algorithm for any number of advertisers for the AdWords problem, however they leave this as a future work, which I find unfortunate. I would recommend taking this direction rigorously and expand the contribution, which would prove to be a very sound contribution.
In order to clarify the exposition the following are some questions:
1. Authors call the approach YaoGAN due to its structural similarity to GANs. I understand the fact that they are training two neural networks in an alternating scheme, which is similar to the GAN training. How can one evaluate the solutions generated by this framework similar to how GAN generators are evaluated? Can one walk the latent distribution of the algorithm agent and draw insights, which might lead into tailoring some algorithms that would be appropriate for some input distribution although in general inferior in terms of worst case guarantees?
2. The main technical contribution claim needs to be elaborated.  I understand how the game theoretic framework is established but how does this manifest itself in the algorithm described in Section 3.1 needs more explanation.
3. Authors claim there are two shortcomings of the previous method proposed in Kong et. al 2018. They need to elaborate how their method overcomes these issues better.
4. Authors state that fractional relaxation of combinatorial mainly integer optimization problems, which is accurate. Yet their approach is only able to solve the fractional version of the AdWords problem. In addition I agree with the fact that although continuous relaxations to integer optimization problems might provide insightful directions they usually employed to to prove bounds on the heuristic approaches. Yet the authors stop at only solving this version with a machine learning approach, which does not hit the bar for me. I would have expected the authors to at least elaborate on why the current framework is not suitable for the non-relaxed problem. What are the shortcomings? 
5.In Appendix A authors talk about no-regret dynamics, which are relevant. However, they state they loosely follow this approach. What does that entail? What kind of theoretical guarantees are given up due to not following this, a better exposition on this topic would help to support the claims.
6. In appendix C.2 authors provide additional plots for the Fractional AdWords problem. However, they retain from providing any intuition about them. In particular what is the conclusion to be drawn from Figure 5.  This needs more elaboration. Is this way of training results expected? What is the lesson learned?
7.In Figure 8 they provide example data from experience array. What are the significance of these examples? How they help us understand the problem instance generation was actually able to find interesting instances? What kind of dynamics are under covered? These are not directly revealed by only looking at the pictures one needs more explanation to support the claims.