More Web Proxy on the site http://driver.im/

research-article

Open access

Online Allocation with Replenishable Budgets: Worst Case and Beyond

Authors:

Mohammad Jaminur Islam,

Shaolei RenAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 8, Issue 1

Article No.: 4, Pages 1 - 34

https://doi.org/10.1145/3639030

Published: 21 February 2024 Publication History

Abstract

This paper studies online resource allocation with replenishable budgets, where budgets can be replenished on top of the initial budget and an agent sequentially chooses online allocation decisions without violating the available budget constraint at each round. We propose a novel online algorithm, called OACP (Opportunistic Allocation with Conservative Pricing), that conservatively adjusts dual variables while opportunistically utilizing available resources. OACP achieves a bounded asymptotic competitive ratio in adversarial settings as the number of decision rounds T gets large. Importantly, the asymptotic competitive ratio of OACP is optimal in the absence of additional assumptions on budget replenishment. To further improve the competitive ratio, we make a mild assumption that there is budget replenishment every T* ≥ 1 decision rounds and propose OACP+ to dynamically adjust the total budget assignment for online allocation. Next, we move beyond the worst-case and propose LA-OACP (Learning-Augmented OACP/OACP+), a novel learning-augmented algorithm for online allocation with replenishable budgets. We prove that LA-OACP can improve the average utility compared to OACP/OACP+ when the ML predictor is properly trained, while still offering worst-case utility guarantees when the ML predictions are arbitrarily wrong. Finally, we run simulation studies of sustainable AI inference powered by renewables, validating our analysis and demonstrating the empirical benefits of LA-OACP.

References

[1]

Shipra Agrawal and Nikhil R Devanur. 2014. Fast algorithms for online stochastic convex programming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. 1405--1424.

[2]

Mohammad Ali Alomrani, Reza Moravej, and Elias Boutros Khalil. 2022. Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach. Transactions on Machine Learning Research (2022). https://openreview.net/forum?id=mbwm7NdkpO

[3]

Brandon Amos, Ivan Jimenez, Jacob Sacks, Byron Boots, and J. Zico Kolter. 2018. Differentiable MPC for End-to-end Planning and Control. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc. https://proceedings.neurips.cc/paper/2018/file/ba6d843eb4251a4526ce65d1807a9309-Paper.pdf

[4]

Brandon Amos and J. Zico Kolter. 2017. OptNet: Differentiable Optimization as a Layer in Neural Networks. In Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 70). PMLR, 136--145.

[5]

Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. 2020. Online Metric Algorithms with Untrusted Predictions. In ICML.

[6]

Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, Vol. 8, 6 (2012), 121--164. https://doi.org/10.4086/toc.2012.v008a006

[7]

Kamiar Asgari and Michael J. Neely. 2020. Bregman-Style Online Convex Optimization with Energy Harvesting Constraints. Proc. ACM Meas. Anal. Comput. Syst., Vol. 4, 3, Article 52 (nov 2020), bibinfonumpages25 pages. https://doi.org/10.1145/3428337

Digital Library

[8]

Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. 2023. Online Resource Allocation under Horizon Uncertainty. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (Orlando, Florida, United States) (SIGMETRICS '23). Association for Computing Machinery, New York, NY, USA, 63--64. https://doi.org/10.1145/3578338.3593559

Digital Library

[9]

Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2020. Dual mirror descent for online allocation problems. In International Conference on Machine Learning. PMLR, 613--628.

[10]

Santiago R Balseiro and Yonatan Gur. 2019. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, Vol. 65, 9 (2019), 3952--3968.

Digital Library

[11]

Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. 2022. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research, Vol. 0, 0 (May 2022), null. https://doi.org/10.1287/opre.2021.2242

Digital Library

[12]

Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. 2020. Exploratory combinatorial optimization with reinforcement learning. In AAAI.

[13]

Dimitri P Bertsekas. 2014. Constrained optimization and Lagrange multiplier methods. Academic press.

[14]

Allan Borodin and Ran El-Yaniv. 2005. Online computation and competitive analysis. cambridge university press.

[15]

Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. 2016. Online Algorithms with Advice: A Survey. SIGACT News, Vol. 47, 3 (Aug. 2016), 93--129.

Digital Library

[16]

Stephen Boyd, Lin Xiao, and Almir Mutapcic. 2003. Subgradient methods. lecture notes of EE392o, Stanford University, Autumn Quarter, Vol. 2004, 01 (2003).

[17]

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 1877--1901. https://proceedings.neurips.cc/paper_files/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf

[18]

Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. 2021. Learning to Optimize: A Primer and A Benchmark. arxiv: 2103.12828 [math.OC]

[19]

Nicolas Christianson, Tinashe Handina, and Adam Wierman. 2022. Chasing Convex Bodies and Functions with Black-Box Advice. In COLT.

[20]

Nikhil R Devanur and Thomas P Hayes. 2009. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce. 71--78.

Digital Library

[21]

Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. 2019. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), Vol. 66, 1 (2019), 1--41.

Digital Library

[22]

Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. 2020. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, Vol. 33 (2020), 8378--8390.

[23]

Bingqian Du, Zhiyi Huang, and Chuan Wu. 2022. Adversarial Deep Learning for Online Resource Allocation. ACM Trans. Model. Perform. Eval. Comput. Syst., Vol. 6, 4, Article 13 (feb 2022), bibinfonumpages25 pages. https://doi.org/10.1145/3494526

Digital Library

[24]

Bingqian Du, Chuan Wu, and Zhiyi Huang. 2019. Learning Resource Allocation and Pricing for Cloud Profit Maximization. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence (Honolulu, Hawaii, USA) (AAAI'19/IAAI'19/EAAI'19). AAAI Press, Article 929, bibinfonumpages8 pages. https://doi.org/10.1609/aaai.v33i01.33017570

Digital Library

[25]

Yonathan Efroni, Shie Mannor, and Matteo Pirotta. 2020. Exploration-exploitation in constrained mdps. arXiv preprint arXiv:2003.02189 (2020).

[26]

Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. 2010. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms. 182--194.

[27]

Jean-Louis Goffin. 1977. On convergence rates of subgradient optimization methods. Mathematical programming, Vol. 13 (1977), 329--347.

[28]

L. Huang. 2020. Fast-Convergent Learning-Aided Control in Energy Harvesting Networks. IEEE Transactions on Mobile Computing, Vol. 19, 12 (dec 2020), 2793--2803. https://doi.org/10.1109/TMC.2019.2936344

[29]

Longbo Huang, Xin Liu, and Xiaohong Hao. 2014. The Power of Online Learning in Stochastic Network Optimization. SIGMETRICS Perform. Eval. Rev., Vol. 42, 1 (June 2014), 153--165.

Digital Library

[30]

Longbo Huang and Michael J. Neely. 2011. Utility Optimal Scheduling in Energy Harvesting Networks. In MobiHoc.

[31]

Stefanus Jasin and Sunil Kumar. 2012. A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, Vol. 37, 2 (2012), 313--345.

Digital Library

[32]

Jiashuo Jiang, Xiaocheng Li, and Jiawei Zhang. 2020. Online Stochastic Optimization with Wasserstein Based Non-stationarity. arXiv preprint arXiv:2012.06961 (2020).

[33]

Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi Yadkori, and Benjamin Van Roy. 2017. Conservative Contextual Linear Bandits. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc. https://proceedings.neurips.cc/paper/2017/file/bdc4626aa1d1df8e14d80d345b2a442d-Paper.pdf

[34]

Zico Kolter, David Duvenaud, and Matt Johnson. http://implicit-layers-tutorial.org/. Deep Implicit Layers.

[35]

Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D. Sivakumar. 2019. A New Dog Learns Old Tricks: RL Finds Classic Optimization Algorithms. In ICLR. https://openreview.net/forum?id=rkluJ2R9KQ

[36]

Ke Li and Jitendra Malik. 2017. Learning to Optimize. In ICLR.

[37]

Pengfei Li, Jianyi Yang, and Shaolei Ren. 2022a. Expert-Calibrated Learning for Online Optimization with Switching Costs. Proc. ACM Meas. Anal. Comput. Syst., Vol. 6, 2, Article 28 (Jun 2022), bibinfonumpages35 pages.

Digital Library

[38]

Pengfei Li, Jianyi Yang, and Shaolei Ren. 2023. Robustified Learning for Online Optimization with Memory Costs. In INFOCOM.

[39]

Tongxin Li, Ruixiao Yang, Guannan Qu, Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. 2022b. Robustness and Consistency in Linear Quadratic Control with Untrusted Predictions. Proc. ACM Meas. Anal. Comput. Syst., Vol. 6, 1, Article 18 (feb 2022), bibinfonumpages35 pages. https://doi.org/10.1145/3508038

Digital Library

[40]

Qiulin Lin, Yanfang Mo, Junyan Su, and Minghua Chen. 2022. Competitive Online Optimization with Multiple Inventories: A Divide-and-Conquer Approach. Proc. ACM Meas. Anal. Comput. Syst., Vol. 6, 2, Article 36 (jun 2022), bibinfonumpages28 pages. https://doi.org/10.1145/3530902

Digital Library

[41]

Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, and Yuanzhang Xiao. 2019. Competitive Online Optimization under Inventory Constraints. Proc. ACM Meas. Anal. Comput. Syst., Vol. 3, 1, Article 10 (mar 2019), bibinfonumpages28 pages. https://doi.org/10.1145/3322205.3311081

Digital Library

[42]

Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. 2021. Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-Varying Constraints. Performance Evaluation, Vol. 152 (2021), 102240. https://doi.org/10.1016/j.peva.2021.102240

Digital Library

[43]

Alexandra Sasha Luccioni, Sylvain Viguier, and Anne-Laure Ligozat. 2023. Estimating the Carbon Footprint of BLOOM, a 176B Parameter Language Model. Journal of Machine Learning Research, Vol. 24, 253, 1--15. http://jmlr.org/papers/v24/23-0069.html

[44]

Thodoris Lykouris and Sergei Vassilvitskii. 2021. Competitive Caching with Machine Learned Advice. J. ACM, Vol. 68, 4, Article 24 (July 2021), bibinfonumpages25 pages.

Digital Library

[45]

M. J. Neely. 2010a. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool.

[46]

Michael J Neely. 2010b. Universal scheduling for networks with arbitrary traffic, channels, and mobility. In 49th IEEE Conference on Decision and Control (CDC). IEEE, 1822--1829.

[47]

California Independent System Operator. 2023. Calfornia Renewable Datasets. https://www.caiso.com/Pages/default.aspx.

[48]

Francesco Orabona. 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213 (2019).

[49]

D. P. Palomar and M. Chiang. 2007. Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications. IEEE Trans. Automatic Control, Vol. 52, 12 (Dec. 2007), 2254--2269.

[50]

Chengrun Qiu, Yang Hu, Yan Chen, and Bing Zeng. 2018. Lyapunov optimization for energy harvesting wireless sensor communications. IEEE Internet of Things Journal, Vol. 5, 3 (2018), 1947--1956.

[51]

Ana Radovanović, Ross Koningstein, Ian Schneider, Bokan Chen, Alexandre Duarte, Binz Roy, Diyue Xiao, Maya Haridasan, Patrick Hung, Nick Care, et al. 2022. Carbon-aware computing for datacenters. IEEE Transactions on Power Systems, Vol. 38, 2 (2022), 1270--1280.

[52]

Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman. 2023. Smoothed Online Optimization with Unreliable Predictions. Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, 1, Article 12 (mar 2023), bibinfonumpages36 pages. https://doi.org/10.1145/3579442

Digital Library

[53]

Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. 2020. Green ai. Commun. ACM, Vol. 63, 12 (2020), 54--63.

Digital Library

[54]

Zhihui Shao, Jianyi Yang, Cong Shen, and Shaolei Ren. 2022. Learning for Robust Combinatorial Optimization: Algorithm and Application. In INFOCOM.

[55]

Kalyan T Talluri, Garrett Van Ryzin, and Garrett Van Ryzin. 2004. The theory and practice of revenue management. Vol. 1. Springer.

[56]

H. R. Varian. 1992. Microeconomic Analysis. W. W. Norton & Company.

[57]

Alexander Wei and Fred Zhang. 2020. Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms. In NeurIPS.

[58]

Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári. 2016. Conservative bandits. In International Conference on Machine Learning. PMLR, 1254--1262.

[59]

Jianyi Yang and Shaolei Ren. 2023. Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints. In AAAI.

[60]

Hao Yu and Michael J Neely. 2019. Learning-aided optimization for energy-harvesting devices with outdated state information. IEEE/ACM Transactions on Networking, Vol. 27, 4 (2019), 1501--1514.

Digital Library

[61]

Hao Yu and Michael J. Neely. 2020. A Low Complexity Algorithm with $mathcalO(sqrtT)$ Regret and $mathcalO(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints. Journal of Machine Learning Research, Vol. 21, 1 (2020), 1--24.

Digital Library

[62]

Han Zhang, Wenzhong Li, Shaohua Gao, Xiaoliang Wang, and Baoliu Ye. 2019. ReLeS: A Neural Adaptive Multipath Scheduler based on Deep Reinforcement Learning. In INFOCOM.

[63]

Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03). 928--936. io

Digital Library

Cited By

Yang JLi PIslam MRen S(2024)Online Allocation with Replenishable Budgets: Worst Case and BeyondACM SIGMETRICS Performance Evaluation Review10.1145/3673660.365507352:1(57-58)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3673660.3655073
Yang JLi PIslam MRen SGaretto MMarin ACiucu FFanti GRighter R(2024)Online Allocation with Replenishable Budgets: Worst Case and BeyondAbstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3652963.3655073(57-58)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3652963.3655073

Index Terms

Online Allocation with Replenishable Budgets: Worst Case and Beyond
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms

Recommendations

Online Allocation with Replenishable Budgets: Worst Case and Beyond
SIGMETRICS '24

This paper studies online resource allocation with replenishable budgets, where budgets can be replenished on top of the initial budget and an agent sequentially chooses online allocation decisions without violating the available budget constraint at ...
Online Allocation with Replenishable Budgets: Worst Case and Beyond
SIGMETRICS/PERFORMANCE '24: Abstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems

This paper studies online resource allocation with replenishable budgets, where budgets can be replenished on top of the initial budget and an agent sequentially chooses online allocation decisions without violating the available budget constraint at ...
Online Budgeted Allocation with General Budgets
EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

We study the online budgeted allocation (also called Adwords) problem, where a set of impressions arriving online are allocated to a set of budget-constrained advertisers to maximize revenue. Motivated by connections to Internet advertising, several ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 8, Issue 1

POMACS

March 2024

494 pages

EISSN:2476-1249

DOI:10.1145/3649331

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California, United States
,
Zhi-Li Zhang
University of Minnesota, United States

Issue’s Table of Contents

Copyright © 2024 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 February 2024

Published in POMACS Volume 8, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
301
Total Downloads

Downloads (Last 12 months)301
Downloads (Last 6 weeks)53

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang JLi PIslam MRen S(2024)Online Allocation with Replenishable Budgets: Worst Case and BeyondACM SIGMETRICS Performance Evaluation Review10.1145/3673660.365507352:1(57-58)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3673660.3655073
Yang JLi PIslam MRen SGaretto MMarin ACiucu FFanti GRighter R(2024)Online Allocation with Replenishable Budgets: Worst Case and BeyondAbstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3652963.3655073(57-58)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3652963.3655073

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents