YaoGAN: Learning Worst-case Competitive Algorithms from Self-generated Inputs
Authors: Goran Zuzic
Di Wang
Aranyak Mehta
D. Sivakumar
Venue:  (2020)

Abstract: 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.    
    

Under review as a conference paper at ICLR 2020
YAOGAN: LEARNING WORST-CASE COMPETITIVE ALGORIHTMS FROM SELF-GENERATED INPUTS
Anonymous authors Paper under double-blind review
ABSTRACT
We tackle the challenge of using machine learning find algorithms with strong worst-case guarantees for online combinatorial optimization problems. Whereas the previous approach along this direction (Kong 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 -rovvddd data beyond specifying the objective of the optimization prob- lem. To answer this question, we draw insights from classic results in game the- ory, analysis of algorithms, and online learning to introduce novel framework. At the high level, similar to a generative adversarial network (GAN), our frame- work has two components whose respective goals are to learn the optimal algo- rithm as well as a set of input instances that captures the essential difficulty of the given optimization problem. The two components 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 be- lieve our new framework points to promising direction which can facilitate the research of algorithm design by leveraging MI. to improve the state of the art both in theory and in practice.
trained against each other
INTRODUCTION
has been a long-standing ambition of machine learning to learn from first principles, that is, machine learning program that learns without any human-provided data beyond an appropriate definition of the task at hand (Silver et al., 2018). The community has made impressive strides towards this goal in recent years, most notably in the domain of tabletop games such as chess, Go, shogi (Silver et al. (018)) and poker (Brown & Sandholm, 2018), where programs have been trained play at superhuman levels without consuming any game-specifie human expertise except, naturally, the rules of the game.
In this work, we look the task of using MI. to design algorithms for optimization problems. Similar to tabletop games, the task of algorithm design has succinct and well-defined objectives, so learning from first principles is potentially feasible. Moreover, the task is very intriguing as typically requires significant amount of time and expertise for humans to accomplish.
In our context, the problem of learning algorithms from first principles is also related an important issue in both ML and algorithms: what input instances is the learned algorithm expected to handle? The typical ML approach is to train the program against a pre-defined training set, with the assump- tion that the training set is carefully chosen to capture future input distributions well, so the learned algorithm generalizes to future input of interest. On the other hand, the algorithm design community in thcoretical computer science (TCS) traditionally considers algorithms with worst-case guarantees due to their robustness against arbitrary input. We focus on the latter domain in our work.
Along the line of learning worst-case algorithms, a particularly relevant result is by Kong et al. (018)) that uses reinforcement learning to learn theoretically optimal algorithms for online opti- mization problems, and one of the key ideas they introduce is the notion of universal and high- entropy training sets. Roughly speaking, such a training set serves as a very effective benchmark in the sense that the task of finding algorithm with strong worst-case guarantee reduces to finding

---

Under review as a conference paper at ICLR 2020
an algorithm that performs well against this training set. Not surprisingly. for given optimization problem, coming up with such a training set can require significant domain expertise a priori. In the current work the goal is to go beyond the framework of universal training sets, and enable learning of algorithms without even this prior domain knowledge.
To overcome this issue, we draw insights from the fields of game theory, analysis of algorithms, and online learning, as well as generative adversarial networks (GANs, [oodffllow et al. (2014). In particular, we introduce a training framework that aims learn a strong worst-case algorithm and an effective benchmark training set simultaneously, all without relying on any human domain expertise beyond specifying how to compute the objective of the optimization problem. If successful, such an approach would have impactful ramifications: researchers could accelerate the speed of discovery by offloading to machines the conecconumingg process of finding problem-specific insights, which can be crucial in improving the state of the art for many problems both in theory and in practice.
At the high level, our framework has two components: the algorithm agent and the adversary. Their goals are to learn the optimal algorithm and set of input instances that captures the essential diffi- culty of the given optimization problem, respectively. For simple optimization problems, rudimen- tary strategies such as random search or grid search can provide a fairly effective adversary. For problems with more interesting underlying space, we exploit deep learning to guide our search for the distribution of difficult inputs. Similar to generative adversarial network (GAN), neural networks, one for the algorithm agent and another for the adversary. We start from scratch, train these two networks against each other, and let them evolve simultaneously. We call our program YaoGAN due to this structural similarity to GAN and the connection to the classic Yao's Lemma (see Section 2.1 for details); this is our main technical contribution.
use two
In this initial effort, we follow Kong et al. 2018) in focusing on online optimization problems (Buch- binder et al. 2009) where each input is sequence arriving over time, and the algorithm needs to make an immediate and irrevocable decision at each time step without knowing the future input. We further restrict our attention to problems that can be solved or approximated by algorithms requir- ing small amount of memory. There are abundant well-studied and interesting problems bearing such properties in online optimization, typically when the structure of the problem exhibits cer- tain Markov property so it is sufficient for the algorithm to maintain succinct state capturing past information.
We consider two online optimization problems, the ski rental problem and the fractional AdWords problem. Ski rental (Karlin et al.) 1986) has been a staple introductory example in online analysis. The second problem, fractional Ad Adrdd (Mehta et al. 20077, is (a fractional relaxation of) well- known problem motivated by online advertising. Moreover, the Adwords problem is closely related to numerous variants of the online bipartite matching problem, which is still an actively studied area in algorithm design, for example in the setting of ride-sharing platforms (Dickerson et al.] 2017] Ashlagi et al. 2019). For these problems, we have good understanding of the structures of the optimal algorithm and difficult inputs, so we can verify that our paradigm leads to something mean- ingful. Our experiments, although fairly limited and preliminary, demonstrate that our framework can be effective at finding algorithms as well as difficult input instances that are consistent with op- timal results. We believe further study along this direction can lead to more exciting developments.
We use generic neural network architecture and ML methods (e.g., Adam optimizer (Kingma & Ba, 2014)) in our experiments, and do not optimize the training set-up or hyperparameters, since our Tocus in this paper is not in extending ML techniques, but in applying our high-level paradigm to learn algorithms from first principles. We believe the co-evolution of new ML techniques tailored to this task will be essential to the ultimate success of this approach. We leave that aspect, as well as applying the framework to more open algorithm design problems, to future work.
Related work. The most relevant paper to ours is an approach by Kong et al. (2018) that uses rein- forcement learning (RL) to find competitive algorithms for online optimization problems including the AdWords problem, online knapsack and the secretary problem. They introduce the notions of universal and high-entropy training set that are tailor-made to facilitate the convergence to worst- case competitive algorithm. Deudon et al. (2018) and Kool et al. (2018) use RL to solve the traveling salesman problem (TSP) in the two-dimensional plane. Both uniformly sample the input points from the unit square and teach the network optimize the expected performance on this input distribution without having access to exact solutions. Nevertheless, the learned algorithms from both approaches
2

---

Under review as a conference paper at ICLR 2020
seem competitive with state-of-the-are methods, at least for modest input sizes. Vinyals et al. (2015) introduce the Pointer Network, a setteencett-sqquene model that successfully manages to approx- imately find convex hulls, Delaunay triangulations and near-optimal planar TSPs. They assume access to an exact solution and use supervised learning to train the model, while their input is uni- formly sampled from the unit square. Grrvvss et al. (2014) introduce the Neural Turing machines, differentiable and computationally universal Turing machine model, and use supervised learning to teach them simple algorithms such as copying or sorting, Kaiser & Sutskever (2015) introduce the parallel and computationally universal Neural GPU and use supervised learning to teach it addition and multiplication that seemingly generalizes to arbitrary lengths.
We point out some other related results without going into details: the work of Bello et al. (2016) studies applying RI. on combinatorial problems including TSP and Knapsack; the work of Dai et al. (2017) exploits embedding and RL to design heuristic algorithms for classic graph problems on specific distributions: BBoutilirr & Lu (016) uses RL. to solve Budget Allocation problem: Duetting et al. (2019) applies deep learning techniques to designing incentive compatible auction mecha- nisms. Readers insterested in ski rental and AdWords can consult Buchhiindrr & Naor (2099) and
Mehta et al. (2013) for more thorough coverage.
To the best of our knowledge, previous results mostly focus on the algorithm side, and either learn algorithms designed to work specific input distributions of interest, utilize supervised learning to mimic a known method, or (in the case of Kong et al. (0188) ) rely on domain expertise to provide hard input instances to train algorithms that competitive in worst-case. We do not wish to detract from the value of optimizing an algorithm on a specific distribution if it is of special interest. Indeed, a practitioner optimizing for distribution D could likely design algorithms that outperform classic solutions on D since classic solutions typically protect against worst-case inputs and might be overly pessimistic on D. Our goal is different: facilitate the discovery of new algorithms with strong worst- case performance on open problems where we do not have a known difficult input distribution at hand. Such learned strategies could then potentially be later fine-tuned to adapt to specific input distributions, while retaining some worst case guarantees.
1.1 SUMMARY OF RESULTS
As brief introduction, we can summarize YaoGANs as essentially starting with a "random" algo- rithm network, then alternating between (1) finding the best response (that will force the algorithm to exhibit its worst behavior), and (2) training the algorithm network on this best response. Details are given in Section
We apply the YaoGAN method to two classic problems in the area of online optimization: the ski rental problem and a fractional version of the AdWordss problem (these are defined formally in Section 2 The two problems exhibit progression in terms of how hard it is to find the "best sponses." Finding best response inputs for ski rental is relatively easy-an an approximately exhaustive search (over suitably parameterized space) is sufficient- while for AdWords it seems to be a hard non-convex global optimization problem.
Ski rental. A few minutes of training leads an algorithm whose competitive ratio- the primary figure of quality for an online optimization algorithm-converee approximately to 1.59, which is within 10-2 2 of the theoretically best value achievable. Furthermore, the behavior of trained algo- rithm exactly matches the one of Karlin et al. (1986) (Appendix C
Fractional AdWords. For the fractional AdWords problem-a "budgeted bipartite matching problem" with 3 advertisers with budget of 3 each and 9 ad slots] about 10 hours of train- ing is sufficient to achieve a competitive ratio of 0.73, which is within 10-2 2 of the theoretically best value achievable for this problem. The trained algorithm qualitatively recovers both the greedy strategy and the balance strategy (Kalyanasundaram & Pruhs 2000), two defining aspects of the op- timal solution, well seems to find the correct form of tradeoff between the strategies in tested scenarios (details in Section[4].
Note that while the problem solved here is defined on "fixed size" instances (27 real numbers), this is already well beyond the regime of executing simple exhaustive search discover the optimal algorithm.
3

---

Under review as a conference paper at ICLR 2020
2 PRELIMINARIES
We start with a discussion of online algorithms and the classic theoretical results upon which we draw insights for our approach. We will keep the discussion high-level and informal since we use these results mostly for intuition rather than extending them to prove any theoretical guarantee.
We chose online optimization problems as the test bed for our approach because they are rich in structure and application. Online problems comprise a theoretical framework to study tasks in the interactive setting. In particular, an algorithm agent is given sequence of requests that require response without knowing future requests. A successful algorithm lypically needs to hedge between receiving immediate reward and allowing for potentially lucrative future rewards. The competitive ratio of an online algorithm for a particular input instance is defined as the ratio of the (expected) objective value the online algorithm gets for the input over the optimal value algorithm can receive for the instance if it knows the entire input upfront (i.e., the offline optimal). The worst- case competitive ratio of an online algorithm its competitive ratio for the worst possible input. We usually drop the "worst-case" when we talk about the competitive ratio of an algorithm. For audience not familiar with the field of online algorithm, we include an expanded background discussion in Appendix
Deep learning approaches typically train a tunable network on a particular distribution of interest. When applied to learning algorithm tion should one train on. Instead, we take a game-theoretic approach that formalizes the interplay between the algorithm and its inputs.
with worst-case guarantees, it is not clear apriori what distribu-
2.1 GAME-THEORENE VIEW
Consider (possibly infinite) two-player zero-sum game matrix V, where we denote the row player as the algorithm player, and the column player as the adversary who determines the inputs to the algorithm. Each row represents a deterministic algorithm A, and each column represents a specific input instance I, and the corresponding entry V(A, specifies the payoff to the adversary if the algorithm player plays strategy A, and the adversary plays strategy I. We follow the custom that the algorithm player aims to minimize the payoff to the adversary, while the adversary tries to achieve the opposite. In the case of online algorithms, if we are working with a problem with minimization objective, the payoff V (A, I) will be the competitive ratio of A for input Z. Similarly, for a maximization problem, we take (AA, I) as the negation of the above competitive ratio.
Yao's Lemma. A randomized algorithm can be viewed as distribution p over rows of V (i.e., deterministic algorithms); a input distribution can be viewed as a distribution over columns of V (i.e., pure inputs). The optimal randomized algorithm p" is one whose expected payoff against the worst-case input is minimized, i.e., p" = arg minp max p" [t, A standard result in game- theory stipulates that in this case maximizing over pure inputs equivalent maximizing over input distributions. The namesake of our paper. Yao's Lemma (Yoo] 1977) (see also Borodin & El- Yaniv (1988) says that there is an adversarial distribution q" over inputs such that the expected payofí of the best deterministic algorithm over q" is the same as the value of the best randomized algorithm p over its worst possible input. In other words, maxy (p") (TV (V,,"" = minA (AA, :" Using classic game theory notations, we also refer to the best randomized algorithm as the row player's minmax strategy, and q² the column player's maxmin strategy.
Solving an online optimization problem corresponds to solving a zero-sum game, i.e., finding both p" and q². Prior work (Kong et al. (018)) explores learning online algorithms by training only the p side. They address the by considering only problems for which the optimal input distribution is known. However, there are two acknowledged weaknesses in this approach:
First, such knowledge of the adversarial maxmin distribution is typically only available for well- studied problems where we already have a theoretically established limit on the performance of any algorithm. Thus, fulfill the ultimate goal of using machine learning discover (unknown) algorithms with competitive "worst-case" performances, we need an approach without relying on domain knowledge of a worst-case input distribution.
Second, a somewhat fundamental issue with the approach is that an algorithm that performs well against the adversarial distribution alone is in fact not necessarily the optimal algorithm. For
4

---

Under review as a conference paper at ICLR 2020
simple example, consider the game of pock-pape--scissors. The maxmin column strategy is to play the three moves uniformly at random, and any row strategy (c.g., always play rock) is a best response to the column player's minmax strategy. Indeed, this was acknowledged in Kong et al. (2018). e.g., for the AdWords problem they combined the adversarial distribution with another hand-picked input distribution to avoid converging
suboptimal greedy algorithm.
As mentioned earlier, our approach avoids these two drawbacks by not trying to come up a good training set upfront, and instead aims to solve for the algorithm's is maxmin solution directly using the framework of no-regret dynamics] B by co-training the adversary and the algorithm.
2.2 SKI RENTAL
We formally define the ski rental problem and illustrate the notions of deterministic strategies and competitive ratios. Randomized and optimal strategies are described in Appendix
Problem 1 (Ski rental) Suppose we want to go skiing in the winter, which requires set of skis. Each day we go skiing, we have two options: either rent the skis for $1, or buy the skis for SB, for some fixed B. Naturally, renting the skis allows to ski only for that one day, while after buying can use them an unlimited number of days. The crux is that we do not know in advance the total number of days l will be able to ski (e.g.. the weather might change, might break a leg, etc.). The objective is to minimize the total amount of money spent by strategically buying/renting skis.
CR of deterministic strategies. A deterministic strategy A takes the form of renting for up to some fixed number of days initially, and if it turns out that we go skiing for at least x days, we buy on day x. If the eventual number of days we go skiing is k; the cost of this strategy will be min (k, B + x 1), and the offline optimal cost will be min(k: [t, B). The corresponding entry in the payoff matrix V is min(k)B+x=-1) and the competitive ratio of this deterministic algorithm is min(k,B)
max min(k, min(k,B B+)=11) i.e. for the worst possible input k. B)
2.3 ADWORDS
We formally define the (non-relaxed) AdWords problem (Mehta al. 2007): There are m adver- tisers with budget B each, and n ad slots. Each ad slot j arrives sequentially along with vector w = =(<0 ......, 1)= where of is the bid of advertiser for slot j. Once a slot arrives the al- gorithm must irrevocably be allocated to an advertiser or no one at all. the event that the ad is allocated to advertiser i, the algorithm collects revenue which the minimum of of and advertiser i's remaining budget. The remaining budget of advertiser is reduced accordingly. The objective of the algorithm is to maximize the total revenue over the entire sequence.
MSVV algorithm. Under a "small bid" assumption, which says that V : of < B, the optimal
online algorithm for AdWords is the following by Mehta et al. 2007). Define s/ := R as the fraction of advertiser i's budget remaining when ad J arrives. Let the "scaled bid" of the slot j for i be of := o/ (1 = The ad slot j is assigned to the advertiser with the largest scaled bid of (with arbitrary tie breaking). The algorithm always guarantees at least a (1 - 1/e) RS 0.632 fraction of the offline optimal revenue, which is asymptotically optimal for large n and m; smaller instances can have better (bigger) CRs.
Here, we will study the fractional version of the problem.
Problem 2 (Fractional AdWords) The fractional problem is the same as in AdWords, except that the algorithm can make fractional allocations. That is, for each ad slot j. the algoritium chooses an assignment (vO- .'. E Rz0 where Σm pi, < 1. The budget of each advertiser with remaining budget r then depleted by min(r.. -x() and the algorithm's 's revenue increased by the same amount (summed over all i).
One way to interpret the fractional AdWords as a discrete AdWords instance is to view each ad j as Q + do infinitesimal sub-slots, and each advertiser has bid D' /Q for each such sub-slot. Under this view, can derive what the optimal algorithm must look like. Suppose the algorithm chooses
5

---

Under review as a conference paper at ICLR 2020
the allocation (Po: pi.... .....). -1) for ad then by considering the MSVV allocation of the "last" infinitesimal sub-slot j. the following optimality condition should hold: all i's where p > must achieve the maximum uy e (<] (122/BB) value (among all advertisers).
Fractional relaxations may sometimes lose some combinatorial flavor of the original problems, but it is meaningful (and common) to study them in algorithm design: often they lead to random- ized algorithms or can be rounded to integral solutions. For Adwords, the fractional version retains the essential characteristics, and the optimal algorithms and hard distributions in fractional and dis- crete cases have a strong connection. The advantage is that the fractional relaxation leads to easy evaluation of the competitive ratio without sampling the policy, which makes the program fully differentiable, and this is very useful for our training framework.
3 YAOGAN
In this work, the goal is to explicitly find the minmax strategy for the row player, by co-training the row and column player networks. YaoGAN facilitates this by training both an algorithm network and an adversarial network. On a conceptual level, YaoGAN alternates between (a) training the adversarial network to produce the best response the algorithm network (in terms of the payoff matrix, i.e., competitive ratios), and (b) training the algorithm network on the generated input. We give brief theoretical motivation behind YaoGANs in Appendix B
3.1 YAOGAN PARADIGM
We instantiate trainable neural network representing the algorithm that starts by outputting mean- ingless (random) values, and our goal is to train it into a competitive algorithm. Similarly, we use some method generate (approximately) best response inputs: This can either be exhaustive search through all deterministic inputs, or can be an trainable adversarial neural network that starts off with outputting meaningless values and can be tuned. We focus on the more interesting, latter, case. Finally, we are given way to evaluate the performance of the algorithm on a input. In the realm of online algorithms this corresponds to running the algorithm network, running solver to compute the offline optimum and then reporting the competitive ratio.
Experience array. We maintain an experience array of input instances that we use to train the algorithm neural network. At each training step of the algorithm, we take some number of samples from the experience array, evaluate the algorithm's 's performances (i.e., the competitive ratio in our case), find the worst input among them for the current algorithm, and train the algorithm against that input.
All instances in the experience array are generated by the adversarial network at some point during the training. At every step the algorithm network is trained against the best response from some number of samples from the experience array. We periodically append new input instances to the experience array, which are chosen among inputs generated by the adversarial network and the samples from the current experience array. We append among these candidates the one that is the best response against the algorithm network.
This stabilizes the training and resolves a multitude of issues. The most apparent being that training the adversarial network to convergence takes significantly more time than one step of the algo- rithm training. Experience arrays amortizes the time spent during adversarial training with an equal amount of algorithmic network training. Furthermore, an empirical issue that has been hindering the training is that the adversarial network can often fail find the best response possible. This not at all unexpected since the question can be in general intractable. Experience arrays allow the adversarial networks to use multiple tries in finding the best counterexample. This counterexample might then be used multiple times since one often needs to train on it few times in succession or revisit it during later training.
One explanation on why such training is effective is that hard distributions often have small support (a small number of different inputs). This is the case in Kong et al. (2018) where the handcrafted adversarial distributions structure might be complex). Furthermore, even if all sets are of large size, one might still find a satisfactory small-set approximation that converges the right set.
often comprised of a small number of different inputs (although their

---

Under review as a conference paper at ICLR 2020
Pseudocode. The pseudocode of YaoGAN is given in Algorithm I We make final note that adversarial network takes dinses-iieal Gaussian noise as input and generates a problem input. The random noise typically attenuated during training, but empirically found that it helped with input space exploration. We use hyperparameters Tbarch = 100, Mmsise 100, Tale = Tadv = 4, Tadd 100, and restart 100. suggested parameters.
The Adam (Kingma & Ba 2014 optimizer is used with paper
Algorithm Generic YaoGAN Training Paradigm.
Require: Differentiable evaluation function V(:.))
Require: Parameters T, Talg. Tadv: Tado, Trestart: Reatch- Instantiate algorithm network ALG, adversarial network ADV Generate Thatch inputs using ADV, and add them to the experience array E.
For f. 1,...,
For u = l Tale
I Thbatch uniformly randomly sampled inputs from E. 8 + arg maxier / V
(AALG,)
Update ALG using Adam (V VALGV(ALG,,")
For u = =. Tadv
Sample Thnatch random Gaussian tensors
Update ADV using Adam( (oanVVDDVV AAVG AD)(=)).
Ift mod Tadd =0 0
Generate 7lbttc inputs using ADV, sample Abatch inputs from E. Among the above inputs, pick the worst one for ALG, append it to E.
If mod Trestant
Reinitialize ADV to produce random (untuned) problem inputs.
4 ADWORDS
In this section, we show how to apply the YaoGAN paradigm to the fractional version of the classic Words problem. The algorithm we derive here will apply to fixed-length inputs. In Appendix C present an application of the YaoGAN paradigm to derive uniform algorithm (one that works for all input lengths) for the ski rental problem.
4.1 DEMONSTRATION OF RESULTS
In this section we demonstrate some qualitative behaviors of our training result. We fix m = 9, 3 and common budget B 3. We defer the representation details to Appendix D.I and extra empirical results to Appendix D.2 About 10 hours of training is sufficient to achieve a competitive
ratio of z 0.7327, which is within 10 of the theoretically best value achievable for this problem.
We start with a brief discussion of the optimal algorithm and input distribution so we can better interpret our results. At high level, there are two intuitive aspects of the AdWords problem (in the discrete case): the greedy strategy and the halance strategy.
Greedy strategy allocates an ad slot to the advertiser with the highest bid for the ad when their remaining budgets are equal. This is natural strategy to maximize revenue.
Balance strategy allocates an ad slot the advertiser with the largest remaining budget when all advertisers have the same bid for the ad. This is also natural to avoid depleting the budget of any advertiser, since we may run into a future ad where only the advertiser with depleted budget has high bid for the ad. The "scaled bid" used in the MSVV algorithm (even for the fractional version) can be viewed as a careful interpolation between two strategics when the advertisers' bids and remaining budgets differ.
We first demonstrate that our trained algorithm captures the "greedy" aspect in Figure I For exam- ple, in the leftmost plot, fix the remaining budgets of all advertisers at 2, the last two advertisers' bid for an ad at 0.25 (the vertical dotted line), and vary the bid x of advertiser 0 to plot the fractional allocations returned by the algorithm for different values. We can that the algorithm correctly
7

---

Under review as a conference paper at ICLR 2020
allocates more to advertiser 0 as the bid increases, and also correctly allocates roughly the most to the advertiser with the highest bid. We observe consistent behavior for other threshold values in the next plots (and more comprchensive plots in the appendix).
Sudgge-
Budget
0.5.0.5. 0...5)
Sudget
Budgee
0.-
06-
0.-
24
244
04
2.4
02-
022
02-
02-
02
Figure 1: Each plot shows the fractional assignment of a new ad the three different advertisers indexed
{0, 1, 1, while keeping the remaining budget equal across all advertisers. The x-axis shows the bid of the first advertiser and the y-axis shows the algorithm agent's fractional assignment p.
We demonstrate the "balance" aspect of our trained algorithm in Figure 2 In the leftmost plot, vary the remaining budget of advertiser 0 while fixing the other advertisers' budget at 0.9, and all advertisers' bids are 1. The algorithm correctly allocates more the advertiser 0 when he/she has more remaining budget, and also correctly gives roughly the most fractional share to the advertiser with largest remaining budget. Again, the observation is consistent in the other plots (and more in the appendix). We note that different from the discrete case where one should expect a sharp transition
Adtowat iast IT's bastgelma, ottwer" busggei- 9. bidu- 3. 3]
Adoentiser I's baadget-X. athers' Inadgel -0 It. 1, 3)
Adlowst iver 2 basigel- oolters buatgal-m S. Ad bad
3.0
3.0
0/2
0.4
0.4
6.5
0.5
06
60
2
Figure 2: Each plot shows the trained agent's allocation of new ad to three different advertisers indexed [0, 2.2. The ad has common bid of 1 from all advertisers. In the hh plot (i E 2, the x-axis denotes the budget of advertiser while other advertisers have common remaining budget. The y-axis shows the algorithm agent's 'ss fractional assignment p.
of allocation around the threshold, the smooth curves observed in our plots actually agree with the optimal algorithm in the fractional case. For concrete example (see Figure 3), we consider the case where the remaining budgets of the advertisers are all fixed at 1, and advertisers have bids (x, 0.5,0) 0) for varying x values. These parameters are chosen for simpler calculation. Let's consider the optimal algorithm's is allocation in this case. From our discussion of the optimal fractional algorithm (immediately following the problem definition of fractional AdWords), we know that the optimal algorithm will split the ad between advertiser 0 and (as advertiser 2 has bid 0), and if the fraction allocated to advertiser 0 is E [0, 1). and 1 - / to advertiser 1, we must have
x (1 e - 0.5 (1
g-
If we use the approximation of - = 1 x for small xr the rough calculation gives as a function 2z
of æ where fractional allocation to advertiser 0 (as a function of æ)) by our trained algorithm is fairly consistent with the optimal.
I++I. We plot this as the dotted (red) curve in Figure 3 and we observe that the
On the adversary side, in the specific case of 3 advertisers and 9 ad slots, an adversarial input distribution (i.e. a minmax column strategy in the game theoretical discussion of Section 2.1 the uniform distribution over the 6 matrices which are the column permutations of the transpose of the following matrix, where ads arrive from top to bottom (left-to-right in the transposed matrix below).
1
1
1
1
17
1 1 1
1
0
0
0
1 1
0
0
0 0
8

---

Under review as a conference paper at ICLR 2020
budgertt, 5..
Figure 3: The plot shows the trained agent's 's allocation of new ad with bids (z, 0.5, 0), where is the value the x-axis and y-axis denotes the fractional assignment All advertisers have common budget of 1. The dotted (red) curve depicts the approximate behavior the optimal algorithm for bidder
the previous work by Kong et al. (2018), they showed that a mixture of an adversarial input distribution and high-entropy (i.e. noisy) distribution gives a sufficiently good (pre-determined) training set. We plot a set of random samples from the experience array at the end of our training in Figure in Appendix D.2 It is clear that without any expert input, the self-generated input instances during training capture enough structure of such an expert crafted mixture. We find this highly non-trivial.
CONCLUSION AND FUTURE DIRECTIONS
In this work explore the idea of using adversarial training for learning optimal algorithms from first principles. We propose the YaoGAN technique and use to recover several near-optimal online algorithms without using any problem-specific domain knowledge about the problem, courtesy of adversarial training. Our results suggest YaoGAN is effective in learning algorithms that are robust worst-case inputs. We also show an important limitation of our approach: The training as effective as the search for best response inputs. When this search can be effectively performed the trained algorithm seem be near optimal; if the search approximate, the algorithms are also approximate.
The ultimate goal of our investigation to gain crucial insight into interesting open problems in previously unexplored ways. While this goal is currently out of reach, we hope our research opens up such a path. On a less ambitious note, our future directions include (1) to use adversarial training to develop algorithm independent of problem size for hard problem such as AdWords, (2) train offline algorithms, and (3) solve general online packing/covering problems as an immediate extension of techniques for AdWords.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta algorithm and applications. Theory of Computing (electronic only], 8, 2012. doi: 10. 10.4086/toc. 2012.v008a000
Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. Edge weighted online windowed matching. In Proceedings of the 2019 ACM Conference Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pp. 729-742, 2019. doi: 10.1145/3328526333297777 URL https:/ /etps://doi..o org 1ttp:/10..111/333333 3329573
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 2016.
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge Uni- versity Press, 1998. ISBN 978-0-521-563924.
Craig Boutilier and Tyler Lu. Budget allocation using weakly coupled, constrained markov decision processes. In UAI, 2016.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93-200 2009. doi: 10.1561/0400000024, URL URL httphhttt////tt http:////.oi..or111..111//11/
wrg.10. 1ttp://11..1111140000000
Niv Buchbinder, Joseph Seffi Naor, et al. The design of competitive online algorithms via a primal- dual approach. Foundations and Trends() in Theoretical Computer Science, 3(2-3):93-263, 2009.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp- 6348-6355 2017.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp.
170-181. Springer, 2018
John Dickerson, Karthik Sankararaman, Aravind Srinivasan, and Pan Xu. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. 2017.
Paul Ductting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 1706-1715, 2019. URL http:tt/ppccceeeeiiee
mlr www.srressseeee wtweees//////duettiinn /tt//tttentnggggggg 9a html
Yoav Freund and Robert E. Schapire. Game theory, on-line prediction and boosting. In Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT 196, pp. 325-332, New York, NY, USA, 1996. ACM. ISBN 0-89791-811-8.
doi: 10. 011144/28861.2388666 URL
http::/ddot acm www.o/gggo......... 1wt.e111112226.11 233166661111113
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Pro- cessing Systems 27, pp. 2672-26622622 2680. Curran Associates, Inc., 2014. URL http: http::/papers.
n nips. hhips.cc/paper//e/ / wwtppperr//2233gerrtatt.... generat ve adversaria -
Alex Graves, Greg Wayne, and Ivo Danihelka. arXiv: 140.541410.5401, 2014.
Neural turing machines. arXiv preprint
10

---

Under review as a conference paper at ICLR 2020
Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint 2015.
Bala Kalyanasundaram and Kirk R. Pruhs. An optimal deterministic algorithm for online b- matching. Theoretical Computer Science, 233())3119 325, 2000. ISSN 0304-3975, doi: hitps: //doi.org/ 10. 10.00.0111100000 01/0://0000000000300799990000000
URL http: /ttp://wwww sci sciencedirecttt.c.cccccccccc com/
A. R. Karlin, M. S. Manasse, L. Rudolph, and Sleator. Competitive snoopy caching. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986), pp. 244 254, Oct 1986. doi: 10.1109/SFCS.198 1986.14..9 14.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 141266944 2014.
Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D Sivakumar. new dog learns old tricks: RI finds classic optimization algorithms. 2018.
Wouter Kool, Herke van Hoof, and Max Welling. Attention solves your tsp, approximately. stat, 1050:22, 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learn- ing Representations, 2018. /
net/ forum ri
Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. ACM, 54(5), October 2007. ISSN 0004-5411. doi: 10.1145/1244320.122
URL
1284321
Aranyak Mehta et al. Online matching and ad allocation. Foundations and Trends()) in Theoretical Computer Science, 8(4):265-368, 2013.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140 1144, 2018.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Anmual Symposium Foundations of Computer Science, SECS '77, pp-
222-227, Washington, DC, USA 1977. IEEE Computer Society. doi: 10.1109/SFCS.197..24 URL httpp:://oi..rg/// 1tt.11109///.1199
A ONLINE ALGORITHM
In this section, we provide more background on the essential notions of online combinatorial opti- mization for the ML audience.
Online algorithm is very different computational model from the classical (offline) algorithm de- sign, and arises broadly in practice in situations where one has make decisions in real time without knowing the future.
In the online context, the input is revealed sequentially instead of once, and the algorithm needs to make irrevocable decisions during the process using the input revealed so far. The difficulty comes from making irrevocable decisions without knowing future input, while the current decision will have implications in the future. Take AdWords as example: the search engine can sell an ad slot (i.e., user impression) each time some user searches for some query. Advertisers specify their budgets (i.e., total amount of money they are willing to spend on all ads) at the beginning of the episode and then place bids each time a new ad slot arrives. The search engine has to decide in real time how to allocate the ad slot advertisers given their bids and budgets. The goal for the
11

---

Under review as a conference paper at ICLR 2020
search engine is to maximize its revenue over the entire input sequence. Once we display the ad from an advertiser, there is no way to change the decision later, and once the budget of an advertiser is depleted, the search engine cannot sell ads to the advertiser any more. See Section 2.3 for formal problem definition.
Inherent difficulties in online optimization. Consider the instance with two bidders A, B both having budget 1, and two ad slots arriving sequentially. Suppose A and B both bid 1 for the first ad. To whom do we allocate the ad? With out loss of generality, suppose we give the first ad A, and collect payment of 1 from A. Now suppose the second ad slot comes, and only A bids 1 for it (and B bids 0). We cannot collect any more revenue from A A's budget is already spent on the first ad, and cannot collect any revenue from B since B values the second ad at O. In this case the total revenue we get is However, hypothetically, if we knew the entire input sequence before making any decision, we could have assigned the ads optimally (the first one to B and the second to A), getting a total revenue 2. This revenue is called the offline optimal, i.e., how well we could have done in retrospect.
Competitive ratio (CR). The main objective for online optimization is to design algorithm with good CR. This is in contrast to (offline) algorithm design where the emphasis is mostly effi ciency. The CR of an algorithm with respect to a particular input is the ratio between the result of the algorithm on this input over the offline optimal of the input. In the above example, we get competitive ratio of 1/2 on that particular instance.
Ad Adversarial model. There are various models specifying what assumptions we have on inputs (i.e., on what inputs we want the algorithm to achieve good CR). c.g. i..d, random order, or adversarial. In this paper we assume the, most general, adversarial model. In it, we want the algorithm to achieve good CR against all possible inputs, and we refer to the CR of an algorithm as the worst CR the algorithm gets on any input. This model achieves the highest level of robustness since it does not put any assumptions on the input; making it a meaningful model to consider in mean real-world settings. For example, in online advertising, the ad slots supply (i.e. user searches) can change drastically when some events go viral. Moreover, advertisers spend great amount of resources to evvess-engginer the search engine's 's algorithm and come up with sophisticated bidding strategies in response. So it is of great interest design algorithm that performs well matter how the inputs look like.
B NO REGRET DYNAMICS AND CONVERGENCE TO THE MINMAX
There is a rich line of work on no regret dynamics (Freund & Schapire 1996 Arora et al. 2012) which lies the center of various fields including game theory, online learning and optimization. In the context of two-player zero-sum games, this gives a method to approximately solve the value of the game without knowing the optimal column player strategy (i.e., the adversarial input distribution) in advance. We extend the notation to use V (pp.q q) to denote p" Vqq.
More specifically, we can let the algorithm player maintain a randomized algorithm p' over iterations I = 1,..., T. In each step the adversary plays the best response I' (i.e. the worst-case input against the algorithm that iteration). The algorithm p*11 then computed from p' and I using a specific no-regret dynamic such as Hedge (Freund & Schapire 1996). Define
p = arg min (p',I'),
q T ΣΣ r
p'
Classic results give us that the payoff of the pair p, q converges to the optimal minmax value for sufficiently large T.
YaoGAN loosely follows this approach. maintains a randomized algorithm p' and searches for the best response I'. However, does not follow the no-regret dynamics of prior algorithms, but rather uses simple gradient descent to optimize the payoff of the algorithm on I'. We avoid going into formal details since use the theoretical guarantees mostly draw insights.
12

---

Under review as a conference paper at ICLR 2020
C
SKI RENTAL
In this section, we derive a uniform algorithm for the classic ski rental problem (defined in Sec- tion 2.2p.
A randomized algorithm for the ski rental problem is represented by a (marginal) probability distri- bution (p). P2:.... ... ..)) with the semantics that for each x {1, 21....... NN), the value Pa, denotes the probability that the we rent skis for the first (up to) x- days and buy skis on day if the season extends that far. For reference, the most interesting case N - oo we note that the optimal choices given by p. = 1 B for = I,..., B, where 1-(1-1/B3B these probabilities sum
to 1. It has a competitive ratio of 1y-B) which tends to 2 1.582 as B + oc (Karlin ct al. 1986).
Our goal here to learn an algorithm that works for all values of B and N + oc. This out of reach for traditional optimization methods for a number of reasons, the most obvious one being the infinite number of variables one needs to optimize over.
For the ski rental problem, we apply simpler variant of the YaoGAN paradigm. Specifically, train a deep neural network to represent the algorithm, but for the adversary, we don't resort to deep neural networks yet. This decouples the algorithmic from the adversarial training and showcases that best-response training is effective. Note that one can still use the full YaoGAN paradigm if one chooses do to so. However, this would be an "overkill" since finding the best response in this case (unlike the AdWords case) is a simple problem where essentially any reasonable method is going to be effective.
As B and N can be (asymptotically) large, we need to work with a continuous space, where every parameter is essentially normalized by N. In this setting, time goes over the range [0, 1] indicating what fraction of the time horizon has passed. At time a E [0, 1]. if we are still skiing, the cost of renting from the beginning of time up to this point captured by a. The cost of buying captured by a real number 3 E [0, 1), which is the fraction of the time one needs to go skiing in order to make buying the skis worthwhile. If we stop skiing at point a of the continuous timeline, the optimal offline cost is min(a,, 3).
Applying the YaoGAN paradigm. On the algorithm side, we train a deep neural network that takes 0 E [0, 1] as inputs, computes the CDF of a probability distribution P3, and outputs the value of the CDF at a. As for the architecture of the algorithm neural network, we use 50 Gaussian kernels N(z;, .) for i 1, .,, 50 with fixed means (i.e., I;'s vi's equally spaced over [0, 1J) and standard deviation o = 2/50, and take a weighted average of these Gaussian kernels as the distributions learned by our neural network. In particular, given any (a, (3) input, the neural network uses / to derive weights wy's 's over the Gaussian kernels (where Σ; wy; 1). and returns the weighted sum of the CDF of these fixed Gaussian kernels at point a as the output of the algorithm. We use fairly generic neural network structure to learn the kernel weights: the network takes (a, as inputs and first applies 4 hidden a-ctiivtie layers with 256 neurons. The last hidden layer, the one that outputs w. is a softmax-activan used to train the network
Adam optimizerKingma & Ba (2014) with the default parameters
On the adversary side, in each training iteration, we randomly sample a small number of values for 3. and for each sampled 3 we use an e-net over [0, 1] as values of a with chosen to be 0.01. We approximately evaluate the competitive ratios (up to certain precision) of the current algorithm for these (a, (3) instances, and train the algorithm neural network with the instance where it gets the worst competitive ratio. The approximation is due to not really taking a integral over the learned edf but rather a step function approximation of it.
We demonstrate the trained algorithm in Figure 4 by instantiating it at various values of B and N. The result is very close to the optimal strategy in all cases, and indicates that our theoretical insight from Section B largely extends to more general settings. We also note here that the competitive ratio achieved by this algorithm converges approximately to 1.59 within a few minutes of training, about 0.01 worse than the optimal value (1.582).
13

---

Under review as a conference paper at ICLR 2020
Rxlk 60300
EACE BuS0
Figure The learnt algorithm instantiated at various (B, values as CDF buying over time (blue curve). The x-axis denotes the number of days the algorithm has seen so far and the y-axis denotes the buying prob- ability. The blue curve is the trained agent's output, while the orange correspond to the theoretical optimal strategy.
D ADWORDS
D.1 ALGORITHM AND ADVERSARY REPRESENTATIONS
In this work we train an algorithm with fixed number of advertisers m 3. Although this is rather limited setting. it captures the essential structure of the problem, and we can observe very non- trivial behavior from both the algorithm side and the input side. There does exist representation for uniform algorithm, i.e., one that works for arbitrary number of m (e.g. see see Kong et al. (2018), and we leave it for future work to extend our framework in that set-up.
Upon the arrival of an ad, the neural network for the algorithm takes as input a vector containing the bids of the advertisers for the current ad and their remaining budgets. The neural network outputs probability distribution (po..... Ps) indicating the fractional allocation of the ad (with ps being the fraction not given to anyone). The network itself is composed of 4 hidden and ReLU-activated layers with 500 neurons succeeded by softmax output layer. The training environment feeds each input instance to the algorithm sequentially, and updates the total revenue and advertisers' remaining budgets along the way with the algorithm outputs.
On the adversary side, we consider inputs with a fixed number of ad slots n = 9, and initial budget B = 3 (both can be changed arbitrary values if needed). The network itself takes Ainoie Gaussian variables, acts upon them using 4 hidden Rel.U-activated layers of 200 neurons each with batch normalization and outputs m X n -attiad-attivated matrix (with outputs [0, 1)).
It is important to note that in this problem (as opposed to the ski-rental problem) there is no easy exhaustive strategy for the adversary side, even with discretization of the weights on the edges there are 27 numbers in an input graph).
D.2 ADDITIONAL PLOTS FOR ADWORDS
Training convergence In Figure 5 the green curve tracks the estimated quality of our trained algorithms saved at different snapshots along training (every 100 training iterations). Note these estimated CR, since the true CR of an algorithm is the worst CR it gets over all possible inputs, but we cannot enumerate over all (infinitely many) possible inputs. Instead, we estimate the CR of each algorithm snapshot using the experience array (generated by the adversarial network) as a benchmark. That is, after training, for each algorithm snapshot we evaluate its CR against all instances in the entire experience array (not the partial experience array at the time of the snapshot), and plot the worst CR it achieves. We expect the green curve to go up, which suggests our algorithm gets better over training. The black dotted line is the CR of the theoretically optimal algorithm, and we see the green curve approaches it. The green curve actually goes slightly above towards the end, which is due to the fact our CRs only estimations, so it can be higher than the true CR for our algorithm if the experience array doesn't 't contain the absolute worst possible input instance for the algorithm.
14

---

Under review as a conference paper at ICLR 2020
0.3
0.2
150
Figure 5: Competitive ratio at snapshots taken just before the adversarial network is restarted. The x-axis represents the snapshot number and the y-axis shows the competitive ratios. The blue (adv) line represents the CR of the fully trained adversarial network before restart. The orange (exp) line at snapshot represents CR the best response from the experience array at snapshot versus trained algorithm at snapshot i. The green (alg) line at snapshot i represents the CR of the hest response from the entire experience array (from the entire training) versus the trained algorithm snapshot i.
Because we can only estimate the CRs, there is the issue of potential collusion. That is, the algorithm network may only find very poor algorithm, but the adversarial network also only generates very easy instances, so the algorithm performs well against generated instances, and thus we get high estimated CRs. In our result, the fact that the estimated CR curve converges to the theoretical optimal CR cases this worry of potential collusion to a large extent, the two networks have no knowledge about this optimal value, thus highly unlikely to generate algorithms and inputs that happen to give that particular estimated CR.
Note this is an intrinsic issue common to problems of such nature. For example, in the case of chess, people estimate the strength of board configuration heuristic search and self-playing. However, this can never eliminate the possibility that an estimated good move lead to loss if the real opponent is much more powerful than the one used in training, and finds a very good counter-move. Similar situation holds in the context of adversarial training (Madry et al.) (2118). In all these cases, all people can do is to try make the adversary side as good as possible during training, so the estimations won't 't be too far off.
move not by any ground truth but by
Algorithm behavior In Figure and Figure 7 we examine the behavior of the learned algorithm upon the arrival of an ad slot. See Section 4 for the qualitative behavior of the theoretically optimal algorithm. In Fi we vary the bids of the advertisers for the ad slot while keeping their remaing budgets the same. Our algorithm clearly demonstrates the greedy behavior (which is the correct strategy in this scenario) of the optimal algorithm. In Figure 7 we fix the bids of all advertisers for the ad slot, and vary their remaining budgets. Our algorithm clearly demonstrates the balance behavior (again the correct strategy in this scenario) of the optimal algorithm. In both figures, the vertical axis is the fractional allocation of the ad slot to the advertisers.
Adversarial distribution We now offer some intuition interpret Figure For AdWords (also holds for fractional AdWords), there is known adversarial distribution over input instances that certifies no algorithm can get better than the optimal CR. Qualitatively, a hard instance follows the pattern that: 1) many advertisers have high bids for the earlier ad slots, and 2) fewer advertisers have high bids for the ad slots arriving later. For such input, if the algorithm is not smart at choosing the allocation for the earlier ads, may deplete the budget of some advertisers, and run into the situation where advertisers with high bids for the later ads already have their budget depleted, while those with remaining budget don't 't value highly of the later ads. If we restrict ourselves to the instances over
15

---

Under review as a conference paper at ICLR 2020
Budget=16.. bidp-ixx
Budget- bidswix
Budlet-1166 bidzeix,
Bucget=>
1M
Dom Rudgee-22 2, bikerls, 0
9wm Budget:2 2, bitertx,
Bwa Risggetm2 2. hifertx, 0.75,
Spm Rucgetm) biderti 10,00
10-
100
05
02
15
Pem. 2udgett2.... Ad bidemls 0.25. 01
Rem. Bodgwtt Ad bidemii 0.5. D1
Rem. Budgwtt22 2.8. bida-tiy 0.75.
Dem: Dww.ett-aaa 2. Ad bida- 1.0.0
10
10
18-
66-
06-
16-
66-
54-
14
62-
82
62-
60
10
30
0.2
Figure 6: Each plot shows the fractional assignment of a new ad the three different advertisers indexed {0, 1, while keeping the remaining budget equal across all advertisers. The bids the incoming ad slot are (I, c, 0). where x changes along the x-axis and e is common for every plot in the same column. The y-axis shows the fractional assignments Each row of plots features advertisers with a common remaining budget.
advertisers and 9 ad slots, concrete instance is given as the triangular matrix at the end of Section (copied below).
1 1
1 1
1
0 0
1
1 1 0
0
0
The 9 ads arrive sequentially from left right, the (i, entry is the bid of advertiser i for ad j. and all advertisers have a budget of 3. However, this instance alone is not enough, since it can be exploited by naive strategy that always allocates ads advertiser 3 (until 3 runs out of budget), then advertiser 2, then advertiser 1. This naive strategy achieves the same as the optimal offline revenue of 9, and thus a competitive ratio of 1 on this one instance. The adversarial distribution is over permutations of the advertisers' names (i.e. rows of the matrix), so naive strategy mentioned before no longer works well.
Figure X plots samples of the "best responses" generated during training. Note these matrices are transposed. In each matrix, ad slots are rows with the top row arriving first, brighter entries mean higher bids (between 0 and 1), and the matrices are ordered by when they are used to train the algo- rithm. Although we don't 't have any quantitative measure, it is fairly clear that the pattern discussed in the previous paragraph emerges as the training evolves. In particular, most of the instances gen- erated later in the training clearly demonstrate the pattern that earlier ads (i.e. top rows) have more advertisers bidding highly (i.e. brighter cells), and later ads have less. Furthermore, we can also see that the adversarial network learns to permute the advertisers (i.e. columns) fairly well. It is very interesting that the adversarial neural network can come up with such pattern from scratch via interactively playing against the algorithm network.
The generated instances are noisy compared to the adversarial distribution in theory (i.e. the triangu- lar matrix and its permutations). This is also the desired behavior as a good training set is expected be high-entropy (see discussion end of Section 4).
16

---

Under review as a conference paper at ICLR 2020
Advertiser O's budget=x.
Advertiser 1's budget=x, others' budget=0.9, Ad b1ds=(1, 1, 1)
Advertiser 2's budget=x.
others' budget=0.9,
others' budget=0.9
Ad (1ds=(1, 1, 1)
Ad bids=(1, 1, 1)
10
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
Advertiser O's budget=x,
Advertiser I's budgetwx, others' budget=1.6.
Advertiser 2's budget=x, others' budget=1.6,
others' budget=1.6.
Ad (1ds= 1, 1)
Ad bids=(1, 1, 1)
Ad bids=(1. 1, 1)
100
10
10
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.0
0.0
0.0
2
2
Advertiser O's budget=x, others' budget=1.6.
Advertiser I's budgetwx, others' budget=1.6,
Advertiser 2's budget others' budget=1.6.
Ad bids=(1, 0)
Ad bids=(1. 1, 0)
Ad bids=(1, 0)
10
10
10
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
Figure Each plot shows the fractional assignment of new adword to the three different advertisers indexed {0, 2). The ad slot has a common bid of to all advertisers. The remaining budgets change for one advertiser along the x axis while staying the same for all other advertisers. The y-axis denotes the fractional assignment
17

---

Under review as a conference paper at ICLR 2020
Figure 8: set of random samples from the experience array after training. The jth row and 8th column represent the bid of advertiser for ad slot j. Darker color represents bid close 0, while brighter color represents bid close to 1.
18


Reviews:
[{"review_id": "rkeZqrk0tr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update to the Review after the rebuttal from the Authors:\nAfter 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.\n \n\nThis 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. \n\nAlthough 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?\n\nThis 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.\n\nIn order to clarify the exposition the following are some questions:\n1. 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?\n\n2. 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.\n\n3. 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.\n\n4. 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? \n\n5.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.\n\n6. 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?\n\n7.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. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkxLGy2ftH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a new approach to solve optimization problems without relying on any human-provided data beyond the specification of the optimization problem itself. The approach is inspired by the two-player zero-sum game paradigm and follow a generative adversarial network (GAN) setting. One network is trained to output the optimal behavior for a given problem, while the other is trained to output difficult instances of the given problem. These two networks are trained simultaneously and compete against the other until some equilibrium is achieved.\nThis approach is tested on two small problems for which the optimal behavior is known and seems to perform near theoretical optimality.\n\nI weakly reject this paper because although the approach is indeed interesting, the paper is lacking some structure, as described below:\n\n- The paper clearly mentions that no optimization of the training setup or the hyperparameters has been done because the authors are not interested in extending ML techniques. However, hyperparameter searching is not extending any ML technique, it is just an approach to find a good training configuration and show robustness in different hyperparameters settings. It is thus unclear if the approach is robust against different hyperparameter settings.\n- Very little details (apart from the optimization algorithm) are given regarding the architecture used (types of input, output, neural units, activation functions, number of hidden layers, loss function, etc...), which makes it very hard to reproduce this approach.\n- Section 1.1 presents results with too many details without introducing the problem. I would suggest the authors to either introduce the two problems earlier or to simply say that near-optimal results are achieved, without giving detailed results, because it is very hard to understand them without any introduction of the task being achieved.\n- One task is presented in Section 2 \"Preliminaries\" while the other task is presented in Section 4 \"AdWords\". It is hard to follow the flow of ideas present in the paper when similar things are not together. I would suggest restructuring the paper into a more classical structure such as: <intro without detailed results - previous work & problematic - approach taken with more details for reproducibility - description of the two tasks - description of experiments with more details for reproducibility - results - conclusion>.\n- The paper mentions the MSVV algorithm twice but no reference or explanation is provided. It is very hard to understand sentences referring to this.\n- This work only considers problems for which the optimal input distribution is known, but is motivated by the fact that it could be applied to problems for which the optimal distribution is unknown and thus being able to discover new algorithms. It is hard to support this motivation when no experiments are done in its favor.\n- No comparison has been made between their approach and other previous approaches. We only know that the proposed approach finds near-optimal solutions with a difference of 0.01 competitive ratio. It is thus very hard to know if this new approach brings any improvement to previous work.\n\nBelow are a few things that were not considered to make a decision, but are only details that would make the paper slightly better:\n- typo at the beginning of section 3.1: missing 'be' in  \"This can either *be* by an ...\"\n- typo at the beginning os section 4:  missing 'be' in \"... the algorithm must irrevocably *be* allocated to ...\"\n- Axis' names to the different plots in the Figures would help understand them better. Also, the description of some figures could benefit more details that could be taken off from the text.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Skgxo_i6_S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This papers tackles the following question. Is it possible to learn the \"most\" complex instance of a class of (combinatorial) problem while finding (or recovering) algorithms with strong minimax rate.\n\nThis is very interesting and clearly a nice line of work (in theory though).\n\nThe techniques used rely on GANs since it can be shown that finding the best (random) algorithm and the worst (deterministic) instance is equivalent to finding the worst random instance against the best deterministic algorithm. This is actually a direct consequence of any minmax theorem in game theory; the authors decided to credit that result to Yao (I tend to *strongly* disagree with that point as, even if he stated this fact in CS, this result was quite standard several decades before him - anyway.).\n\nThen this idea is evaluated in two examples. A toy problem (the ski rental) and a more or less concrete ones (adwords pb of Mehta). This is the major disappointment in the paper. The basic idea is very interesting, but I would have expect more interesting use cases as teased by the first sentence of the abstract \"find algorithms with strong worst-case guarantees for online combinatorial optimization problems\".\n\nSo at the end, I am a bit puzzled. I really like the idea, but I have the feeling that this technique should have been developed for more complicated setting. Or maybe it is actually not working on more difficult combinatorial problem (and this is hidden in the paper). I believe that this paper is thus not in its final form and could be largely improved.\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose an intriguing way to designing competitive online algorithms. However, the state of the paper and the provided evidence of the success of the proposed methodology is too preliminary to merit acceptance.
Decision: Reject