{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:03:49Z","timestamp":1775815429793,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T00:00:00Z","timestamp":1745280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,4,22]]},"DOI":"10.1145\/3696410.3714881","type":"proceedings-article","created":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T22:47:11Z","timestamp":1745362031000},"page":"1398-1415","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3296-4891","authenticated-orcid":false,"given":"Gagan","family":"Aggarwal","sequence":"first","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4920-478X","authenticated-orcid":false,"given":"Giannis","family":"Fikioris","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8008-0922","authenticated-orcid":false,"given":"Mingfei","family":"Zhao","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Gagan Aggarwal Giannis Fikioris and Mingfei Zhao. 2024. No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints. arxiv: 2404.09832 [cs.GT] https:\/\/arxiv.org\/abs\/2404.09832"},{"key":"e_1_3_2_1_2_1","volume-title":"ACM Conference on Economics and Computation, EC","author":"Agrawal Shipra","year":"2014","unstructured":"Shipra Agrawal and Nikhil R. Devanur. 2014. Bandits with concave rewards and convex knapsacks. In ACM Conference on Economics and Computation, EC 2014. ACM, Stanford, CA, USA, 989--1006."},{"key":"e_1_3_2_1_3_1","volume-title":"Devanur","author":"Agrawal Shipra","year":"2016","unstructured":"Shipra Agrawal and Nikhil R. Devanur. 2016. Linear Contextual Bandits with Knapsacks. In Neural Information Processing Systems, NeurIPS 2016. Curran Associates Inc., Barcelona, Spain, 3450--3458."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_3_2_1_5_1","volume-title":"Bandits with Knapsacks. In Symposium on Foundations of Computer Science, FOCS","author":"Badanidiyuru Ashwinkumar","year":"2013","unstructured":"Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. 2013. Bandits with Knapsacks. In Symposium on Foundations of Computer Science, FOCS 2013. IEEE Computer Society, Berkeley, CA, USA, 207--216."},{"key":"e_1_3_2_1_6_1","volume-title":"Neural Information Processing Systems, NeurIPS","author":"Balseiro Santiago R.","year":"2019","unstructured":"Santiago R. Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab S. Mirrokni, and Jon Schneider. 2019. Contextual Bandits with Cross-Learning. In Neural Information Processing Systems, NeurIPS 2019. Curran Associates Inc., Red Hook, NY, USA, 9676--9685."},{"key":"e_1_3_2_1_7_1","volume-title":"Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. In ACM Conference on Economics and Computation, EC","author":"Santiago","year":"2017","unstructured":"Santiago R. Balseiro and Yonatan Gur. 2017. Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. In ACM Conference on Economics and Computation, EC 2017. ACM, Cambridge, MA, USA, 609."},{"key":"e_1_3_2_1_8_1","volume-title":"Dual Mirror Descent for Online Allocation Problems. In International Conference on Machine Learning, ICML","volume":"119","author":"Balseiro Santiago R.","year":"2020","unstructured":"Santiago R. Balseiro, Haihao Lu, and Vahab S. Mirrokni. 2020. Dual Mirror Descent for Online Allocation Problems. In International Conference on Machine Learning, ICML 2020, Vol. 119. PMLR, Virtual Event, 613--628."},{"key":"e_1_3_2_1_9_1","volume-title":"International Conference on Learning Representations, ICLR","author":"Bernasconi Martino","year":"2024","unstructured":"Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. 2024. Bandits with Replenishable Knapsacks: the Best of both Worlds. In International Conference on Learning Representations, ICLR 2024. OpenReview.net, Vienna, Austria."},{"key":"e_1_3_2_1_10_1","volume-title":"Online Learning with Knapsacks: the Best of Both Worlds. In International Conference on Machine Learning, ICML","volume":"162","author":"Castiglioni Matteo","year":"2022","unstructured":"Matteo Castiglioni, Andrea Celli, and Christian Kroer. 2022. Online Learning with Knapsacks: the Best of Both Worlds. In International Conference on Machine Learning, ICML 2022, Vol. 162. PMLR, Baltimore, Maryland, USA, 2767--2783."},{"key":"e_1_3_2_1_11_1","volume-title":"International Conference on Machine Learning, ICML","author":"Castiglioni Matteo","year":"2024","unstructured":"Matteo Castiglioni, Andrea Celli, and Christian Kroer. 2024. Online Learning under Budget and ROI Constraints via Weak Adaptivity. In International Conference on Machine Learning, ICML 2024. OpenReview.net, Vienna, Austria."},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017","volume":"65","author":"Cesa-Bianchi Nicol\u00f2","year":"2017","unstructured":"Nicol\u00f2 Cesa-Bianchi, Pierre Gaillard, Claudio Gentile, and S\u00e9bastien Gerchinovitz. 2017. Algorithmic Chaining and the Role of Partial Feedback in Online Nonparametric Learning. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Vol. 65. PMLR, Amsterdam, The Netherlands, 465--481."},{"key":"e_1_3_2_1_13_1","volume-title":"Online Bidding Algorithms for Return-on-Spend Constrained Advertisers. In ACM Web Conference 2023, WWW 2023. ACM","author":"Feng Zhe","year":"2023","unstructured":"Zhe Feng, Swati Padmanabhan, and Di Wang. 2023. Online Bidding Algorithms for Return-on-Spend Constrained Advertisers. In ACM Web Conference 2023, WWW 2023. ACM, Austin, TX, USA, 3550--3560."},{"key":"e_1_3_2_1_14_1","volume-title":"Approximately Stationary Bandits with Knapsacks. In Conference on Learning Theory, COLT","volume":"195","author":"Giannis","year":"2023","unstructured":"Giannis Fikioris and \u00c9va Tardos. 2023a. Approximately Stationary Bandits with Knapsacks. In Conference on Learning Theory, COLT 2023, Vol. 195. PMLR, Bangalore, India, 3758--3782."},{"key":"e_1_3_2_1_15_1","volume-title":"Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions. In ACM Conference on Economics and Computation, EC","author":"Giannis","year":"2023","unstructured":"Giannis Fikioris and \u00c9va Tardos. 2023b. Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions. In ACM Conference on Economics and Computation, EC 2023. ACM, London, United Kingdom, 678--698."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_1_18_1","volume-title":"Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In Innovations in Theoretical Computer Science Conference, ITCS","volume":"251","author":"Gaitonde Jason","year":"2023","unstructured":"Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. 2023. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In Innovations in Theoretical Computer Science Conference, ITCS 2023, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, MIT, Cambridge, Massachusetts, USA, 52:1--52:1."},{"key":"e_1_3_2_1_19_1","volume-title":"Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions. CoRR","author":"Han Yanjun","year":"2020","unstructured":"Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. 2020. Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions. CoRR, Vol. abs\/2007.04568 (2020). showeprint[arXiv]2007.04568"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_3_2_1_21_1","volume-title":"Adversarial Bandits with Knapsacks. In Symposium on Foundations of Computer Science, FOCS","author":"Immorlica Nicole","year":"2019","unstructured":"Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, and Aleksandrs Slivkins. 2019. Adversarial Bandits with Knapsacks. In Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, Baltimore, Maryland, USA, 202--219."},{"key":"e_1_3_2_1_22_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"Richard","year":"2007","unstructured":"Richard M. Karp and Robert Kleinberg. 2007. Noisy binary search and its applications. In ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. SIAM, New Orleans, Louisiana, USA, 881--890."},{"key":"e_1_3_2_1_23_1","volume-title":"Online Learning with Vector Costs and Bandits with Knapsacks. In Conference on Learning Theory, COLT","volume":"125","author":"Kesselheim Thomas","year":"2020","unstructured":"Thomas Kesselheim and Sahil Singla. 2020. Online Learning with Vector Costs and Bandits with Knapsacks. In Conference on Learning Theory, COLT 2020, Vol. 125. PMLR, Virtual Event [Graz, Austria], 2286--2305."},{"key":"e_1_3_2_1_24_1","volume-title":"Symposium on Foundations of Computer Science, FOCS","author":"Robert","year":"2003","unstructured":"Robert D. Kleinberg and Frank Thomson Leighton. 2003. The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. In Symposium on Foundations of Computer Science, FOCS 2003. IEEE Computer Society, Cambridge, Massachusettes, USA, 594--605."},{"key":"e_1_3_2_1_25_1","volume-title":"Neural Information Processing Systems, NeurIPS","author":"Kumar Raunak","year":"2022","unstructured":"Raunak Kumar and Robert Kleinberg. 2022. Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem. In Neural Information Processing Systems, NeurIPS 2022. Curran Associates Inc., New Orleans, LA, USA, 12 pages."},{"key":"e_1_3_2_1_26_1","volume-title":"Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions. In ACM Conference on Economics and Computation,EC","author":"Kumar Rachitesh","year":"2024","unstructured":"Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. 2024. Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions. In ACM Conference on Economics and Computation,EC 2025. Association for Computing Machinery, New York, NY, USA, 893."},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory, COLT","volume":"247","author":"Lucier Brendan","year":"2024","unstructured":"Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. 2024. Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics. In Conference on Learning Theory, COLT 2023, Vol. 247. PMLR, Bangalore, India, 3642--3643."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3440959.3440965"},{"key":"e_1_3_2_1_29_1","volume-title":"Conference on Learning Theory, COLT","volume":"195","author":"Slivkins Aleksandrs","year":"2023","unstructured":"Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J. Foster. 2023. Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression. In Conference on Learning Theory, COLT 2023, Vol. 195. PMLR, Bangalore, India, 4633--4656."},{"key":"e_1_3_2_1_30_1","first-page":"596","article-title":"Weak convergence and empirical processes with applications to statistics","volume":"160","author":"van der Vaart AW","year":"1997","unstructured":"AW van der Vaart and Jon A Wellner. 1997. Weak convergence and empirical processes with applications to statistics. Journal of the Royal Statistical Society-Series A Statistics in Society, Vol. 160, 3 (1997), 596--608.","journal-title":"Journal of the Royal Statistical Society-Series A Statistics in Society"},{"key":"e_1_3_2_1_31_1","volume-title":"International Conference on Machine Learning, ICML","volume":"202","author":"Wang Qian","year":"2023","unstructured":"Qian Wang, Zongjun Yang, Xiaotie Deng, and Yuqing Kong. 2023. Learning to Bid in Repeated First-Price Auctions with Budgets. In International Conference on Machine Learning, ICML 2023, Vol. 202. PMLR, Honolulu, Hawaii, 36494--36513."},{"key":"e_1_3_2_1_32_1","volume-title":"Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In International Conference on Machine Learning, ICML","author":"Zinkevich Martin","year":"2003","unstructured":"Martin Zinkevich. 2003. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In International Conference on Machine Learning, ICML 2023. AAAI Press, Washington, DC, USA, 928--936."}],"event":{"name":"WWW '25: The ACM Web Conference 2025","location":"Sydney NSW Australia","acronym":"WWW '25","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"]},"container-title":["Proceedings of the ACM on Web Conference 2025"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714881","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696410.3714881","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:53Z","timestamp":1750295933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714881"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":32,"alternative-id":["10.1145\/3696410.3714881","10.1145\/3696410"],"URL":"https:\/\/doi.org\/10.1145\/3696410.3714881","relation":{},"subject":[],"published":{"date-parts":[[2025,4,22]]},"assertion":[{"value":"2025-04-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}