A NEW DOG LEARNS OLD TRICKS: RL FINDS CLASSIC OPTIMIZATION ALGORITHMS
We ask whether reinforcement learning can find theoretically optimal algorithms for online optimization problems, and introduce a novel learning framework in this setting. To answer this question, we introduce a number of key ideas from traditional algorithms and complexity theory. Specifically, we introduce the concept of adversarial distributions (universal and high-entropy training sets), which are distributions that encourage the learner to find algorithms that work well in the worst case. We test our new ideas on the AdWords problem, the online knapsack problem, and the secretary problem. Our results indicate that the models have learned behaviours that are consistent with the optimal algorithms for these problems derived using the online primal-dual framework.
The overall goal of this paper is to solve online combinatorial optimization (OCO) problems using reinforcement learning. Importantly, the authors are not seeking to establish new results for unsolved problems, but instead they are motivated by analyzing and comparing the quality of solutions predicted by reinforcement learners with respect to the well-known near-optimal strategies for some OCO tasks. In doing so, the authors focused on an MDP framework using policy gradient and DQN methods. This framework was trained on three OCO tasks; online budget allocation, online knapsack, and the secretary problem. For each, the trained model is consistent with the near-optimal “handcrafted’’ algorithms.
The idea of checking whether a standard RL framework, without prior information about “how to” solve a given OCO task, is capable from experience to reach the performance of existing optimal strategies (especially primal-dual approaches), is clearly interesting. But I am not entirely convinced that the paper is making novel contributions in this direction. My comments are detailed below:
(1) OCO problems have been a subject of extensive research in online learning (see e.g. [1,2,3]). Notably, the main issues related to “input length independence” (Sec 1.1) and “adversarially chosen input distributions” (Sec 1.2) have already been addressed in online learning frameworks. Input length independence is related to “horizon-independence” in online learning (the number $T$ of trials is not known in advance), and well-known approaches have been developed for devising horizon-independent forecasters, or transforming a horizon-dependent forecaster into a horizon-independent one (see e.g. [4]). Also, the study of online learners with respect to different properties of input sequences (stochastic, adversarial, or hybrid), is a well-known topic of research which have been conceptualized and formalized with appropriate metrics (see e.g. [5,6]). 
(2) Although the authors are interested in making connection between RL and “primal-dual approaches” in online learning, this connection was not made clear in the paper. Namely, the overall contribution was to show that deep RL architectures can compete with existing, handcrafted online strategies, on three specific tasks. But in order to make a concrete connection with primal-dual approaches, this study should be extended to more general primal (covering) and dual (packing) problems as described in [7], and the RL framework should be compared with “generic” online primal-dual algorithms also described in [7]. We may note in passing that the offline versions of the three tasks examined in the present paper belong to the approximation classes PTAS or APX. By contrast, the complexity class of general covering/packing problems is much higher (a constant approximation ratio is not achievable unless P=NP) and, to this point, it would be interesting to examine whether a standard deep RL framework can compete with existing online strategies (for example in [7,8]) on such hard problems.
(3) Even if we stick to the three problems examined in the paper, the neural nets vary between tasks, with different numbers of layers, different widths, different batch sizes, etc. On the one hand, it is legitimate to seek for an appropriate learning architecture for the input problem. On the other hand, such adjustments are conveying some prior knowledge about “how to” solve this problem using a deep RL model. Moreover, for knapsack and secretary tasks, additional knowledge about the history (i.e. state augmentation) is required for establishing convergence, but the resulting model is no longer a standard MDP. So, unless I missed the point about the overall goal of this paper, these different aspects are somewhat in contradiction with the idea of starting with a deep RL architecture with default settings, in which the varying components are essentially the states, transitions, and rewards of the MDP that encodes the problem description. 
[1] Bubeck, S., Introduction to Online Optimization. Lecture Notes, Princeton University, 2011.
[2] Audibert, J-Y., Bubeck, S., and Lugosi, G. Minimax policies for combinatorial prediction games. In COLT, 2011.
[3] Rajkumar, A. and Agarwal, S. Online decision-making in general combinatorial spaces. In NIPS, 2014.
[4] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[5] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. In NIPS, 2011.
[6] N. Buchbinder, S. Chen, J. Naor, O. Shamir: Unified Algorithms for Online Learning and Competitive Analysis. In COLT, 2012.
[7] N. Buchbinder and J. Naor. The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in Theoretical Computer Science, 2009.
[8] S. Arora, E. Hazan, and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications, Theory of Computing, 2012.