{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,9]],"date-time":"2026-09-09T13:56:18Z","timestamp":1788962178416,"version":"build-2803163510"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T00:00:00Z","timestamp":1640908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["HKU 17204619, 17208920, and C5026-18G (CRF)"],"award-info":[{"award-number":["HKU 17204619, 17208920, and C5026-18G (CRF)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>Online algorithms are an important branch in algorithm design. Designing online algorithms with a bounded competitive ratio (in terms of worst-case performance) can be hard and usually relies on problem-specific assumptions. Inspired by adversarial training from Generative Adversarial Net and the fact that the competitive ratio of an online algorithm is based on worst-case input, we adopt deep neural networks (NNs) to learn an online algorithm for a resource allocation and pricing problem from scratch, with the goal that the performance gap between offline optimum and the learned online algorithm can be minimized for worst-case input.<\/jats:p>\n          <jats:p>Specifically, we leverage two NNs as the algorithm and the adversary, respectively, and let them play a zero sum game, with the adversary being responsible for generating worst-case input while the algorithm learns the best strategy based on the input provided by the adversary. To ensure better convergence of the algorithm network (to the desired online algorithm), we propose a novel per-round update method to handle sequential decision making to break complex dependency among different rounds so that update can be done for every possible action instead of only sampled actions. To the best of our knowledge, our work is the first using deep NNs to design an online algorithm from the perspective of worst-case performance guarantee. Empirical studies show that our updating methods ensure convergence to Nash equilibrium and the learned algorithm outperforms state-of-the-art online algorithms under various settings.<\/jats:p>","DOI":"10.1145\/3494526","type":"journal-article","created":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T09:11:46Z","timestamp":1644311506000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Adversarial Deep Learning for Online Resource Allocation"],"prefix":"10.1145","volume":"6","author":[{"given":"Bingqian","family":"Du","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhiyi","family":"Huang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chuan","family":"Wu","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,2,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_3_2","article-title":"A brief survey of deep reinforcement learning","author":"Arulkumaran Kai","year":"2017","unstructured":"Kai Arulkumaran, Marc Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. 2017. A brief survey of deep reinforcement learning. arXiv preprint arXiv:1708.05866.","journal-title":"arXiv preprint arXiv:1708.05866"},{"key":"e_1_3_2_4_2","unstructured":"Siddhartha Banerjee Itai Gurvich and Alberto Vera. 2020. Constant Regret in Online Allocation: On the Sufficiency of a Single Historical Trace . https:\/\/people.orie.cornell.edu\/ig264\/Online_Optimization_with_Samples.pdf."},{"key":"e_1_3_2_5_2","article-title":"Neural combinatorial optimization with reinforcement learning","author":"Bello Irwan","year":"2016","unstructured":"Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. 2016. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.","journal-title":"arXiv preprint arXiv:1611.09940"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294260"},{"key":"e_1_3_2_7_2","article-title":"Large scale GAN training for high fidelity natural image synthesis","author":"Brock Andrew","year":"2018","unstructured":"Andrew Brock, Jeff Donahue, and Karen Simonyan. 2018. Large scale GAN training for high fidelity natural image synthesis. arXiv preprint arXiv:1809.11096.","journal-title":"arXiv preprint arXiv:1809.11096"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_3_2_11_2","article-title":"Coordination in adversarial sequential team games via multi-agent deep reinforcement learning","author":"Celli Andrea","year":"2019","unstructured":"Andrea Celli, Marco Ciccone, Raffaele Bongo, and Nicola Gatti. 2019. Coordination in adversarial sequential team games via multi-agent deep reinforcement learning. arXiv preprint arXiv:1912.07712.","journal-title":"arXiv preprint arXiv:1912.07712"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33017570"},{"key":"e_1_3_2_13_2","first-page":"2319","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Gollapudi Sreenivas","year":"2019","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In Proceedings of the International Conference on Machine Learning. 2319\u20132327."},{"key":"e_1_3_2_14_2","article-title":"NIPS 2016 tutorial: Generative adversarial networks","author":"Goodfellow Ian","year":"2016","unstructured":"Ian Goodfellow. 2016. NIPS 2016 tutorial: Generative adversarial networks. arXiv preprint arXiv:1701.00160.","journal-title":"arXiv preprint arXiv:1701.00160"},{"key":"e_1_3_2_15_2","first-page":"2672","volume-title":"Advances in Neural Information Processing Systems","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. In Advances in Neural Information Processing Systems. 2672\u20132680."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18318-8"},{"key":"e_1_3_2_17_2","article-title":"Erdos goes neural: An unsupervised learning framework for combinatorial optimization on graphs","author":"Karalias Nikolaos","year":"2020","unstructured":"Nikolaos Karalias and Andreas Loukas. 2020. Erdos goes neural: An unsupervised learning framework for combinatorial optimization on graphs. arXiv preprint arXiv:2006.10643.","journal-title":"arXiv preprint arXiv:2006.10643"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7_9"},{"key":"e_1_3_2_19_2","first-page":"6348","volume-title":"Advances in Neural Information Processing Systems","author":"Khalil Elias","year":"2017","unstructured":"Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems. 6348\u20136358."},{"key":"e_1_3_2_20_2","article-title":"Attention, learn to solve routing problems!","author":"Kool Wouter","year":"2018","unstructured":"Wouter Kool, Herke Van Hoof, and Max Welling. 2018. Attention, learn to solve routing problems!arXiv preprint arXiv:1803.08475.","journal-title":"arXiv preprint arXiv:1803.08475"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/3327546.3327635"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/3322706.3362025"},{"key":"e_1_3_2_23_2","first-page":"539","volume-title":"Advances in Neural Information Processing Systems","author":"Li Zhuwen","year":"2018","unstructured":"Zhuwen Li, Qifeng Chen, and Vladlen Koltun. 2018. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems. 539\u2013548."},{"key":"e_1_3_2_24_2","first-page":"907","volume-title":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics","author":"Liang Tengyuan","year":"2019","unstructured":"Tengyuan Liang and James Stokes. 2019. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. 907\u2013915."},{"key":"e_1_3_2_25_2","article-title":"Policy iteration Q-learning for data-based two-player zero-sum game of linear discrete-time systems","author":"Luo Biao","year":"2020","unstructured":"Biao Luo, Yin Yang, and Derong Liu. 2020. Policy iteration Q-learning for data-based two-player zero-sum game of linear discrete-time systems. IEEE Transactions on Cybernetics 51, 7 (2020), 3630\u20133640.","journal-title":"IEEE Transactions on Cybernetics"},{"key":"e_1_3_2_26_2","first-page":"3296","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive caching with machine learned advice. In Proceedings of the International Conference on Machine Learning. 3296\u20133305."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3005745.3005750"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585758"},{"key":"e_1_3_2_29_2","article-title":"Revenue optimization with approximate bid predictions","author":"Medina Andr\u00e9s Munoz","year":"2017","unstructured":"Andr\u00e9s Munoz Medina and Sergei Vassilvitskii. 2017. Revenue optimization with approximate bid predictions. arXiv preprint arXiv:1706.04732 (2017).","journal-title":"arXiv preprint arXiv:1706.04732"},{"key":"e_1_3_2_30_2","article-title":"Conditional generative adversarial nets","author":"Mirza Mehdi","year":"2014","unstructured":"Mehdi Mirza and Simon Osindero. 2014. Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784.","journal-title":"arXiv preprint arXiv:1411.1784"},{"key":"e_1_3_2_31_2","article-title":"Gradient descent GAN optimization is locally stable","author":"Nagarajan Vaishnavh","year":"2017","unstructured":"Vaishnavh Nagarajan and J. Zico Kolter. 2017. Gradient descent GAN optimization is locally stable. arXiv preprint arXiv:1706.04156 (2017).","journal-title":"arXiv preprint arXiv:1706.04156"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66179-7_48"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2008.11.002"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature24270"},{"key":"e_1_3_2_35_2","volume-title":"Mathematics for Economists","year":"1994","unstructured":"Carl P. Simon and Lawrence Blume. 1994. Mathematics for Economists. Vol. 7. Norton, New York, NY."},{"key":"e_1_3_2_36_2","article-title":"Nash convergence of gradient dynamics in iterated general-sum games","author":"Singh Satinder","year":"2013","unstructured":"Satinder Singh, Michael Kearns, and Yishay Mansour. 2013. Nash convergence of gradient dynamics in iterated general-sum games. arXiv preprint arXiv:1301.3892.","journal-title":"arXiv preprint arXiv:1301.3892"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_38_2","article-title":"DREAM: Deep regret minimization with advantage baselines and model-free learning","author":"Steinberger Eric","year":"2020","unstructured":"Eric Steinberger, Adam Lerer, and Noam Brown. 2020. DREAM: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006.10410.","journal-title":"arXiv preprint arXiv:2006.10410"},{"key":"e_1_3_2_39_2","unstructured":"Gerald Tesauro. 2005. Online resource allocation using decompositional reinforcement learning. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI\u201905) . 886\u2013891."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2061"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011401"},{"key":"e_1_3_2_42_2","article-title":"Automated cloud provisioning on AWS using deep reinforcement learning","author":"Wang Zhiguang","year":"2017","unstructured":"Zhiguang Wang, Chul Gwon, Tim Oates, and Adam Iezzi. 2017. Automated cloud provisioning on AWS using deep reinforcement learning. arXiv preprint arXiv:1709.04305.","journal-title":"arXiv preprint arXiv:1709.04305"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10804"},{"key":"e_1_3_2_44_2","volume-title":"Proceedings of the NIPS Workshop on Adversarial Training","volume":"21","author":"Zhang Yizhe","year":"2016","unstructured":"Yizhe Zhang, Zhe Gan, and Lawrence Carin. 2016. Generating text via adversarial training. In Proceedings of the NIPS Workshop on Adversarial Training, Vol. 21."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3084460"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_63"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494526","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:43Z","timestamp":1750193323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,31]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3494526"],"URL":"https:\/\/doi.org\/10.1145\/3494526","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"value":"2376-3639","type":"print"},{"value":"2376-3647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,31]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}