{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:45Z","timestamp":1750309545729,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":53,"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"}],"funder":[{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["ONR N00014-23-1-2299"],"award-info":[{"award-number":["ONR N00014-23-1-2299"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF CCF-2112665"],"award-info":[{"award-number":["NSF CCF-2112665"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,4,28]]},"DOI":"10.1145\/3696410.3714734","type":"proceedings-article","created":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T16:42:02Z","timestamp":1746463322000},"page":"3096-3107","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Bidding under RoS Constraints without Knowing the Value"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9794-9575","authenticated-orcid":false,"given":"Sushant","family":"Vijayan","sequence":"first","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6036-375X","authenticated-orcid":false,"given":"Zhe","family":"Feng","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4834-2136","authenticated-orcid":false,"given":"Swati","family":"Padmanabhan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2879-5868","authenticated-orcid":false,"given":"Karthikeyan","family":"Shanmugam","sequence":"additional","affiliation":[{"name":"Google DeepMind, Bengaluru, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4113-5924","authenticated-orcid":false,"given":"Arun","family":"Suggala","sequence":"additional","affiliation":[{"name":"Google DeepMind, Bengaluru, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0891-0255","authenticated-orcid":false,"given":"Di","family":"Wang","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Virtual Conference, Worldwide (Proceedings of Machine Learning Research),, Vitaly Feldman, Katrina Ligett, and Sivan Sabato (Eds.)","volume":"132","author":"Achddou Juliette","year":"2021","unstructured":"Juliette Achddou, Olivier Capp\u00e9, and Aur\u00e9lien Garivier. 2021. Efficient Algorithms for Stochastic Repeated Second-price Auctions. In Algorithmic Learning Theory, 16--19 March 2021, Virtual Conference, Worldwide (Proceedings of Machine Learning Research),, Vitaly Feldman, Katrina Ligett, and Sivan Sabato (Eds.), Vol. 132. PMLR, 99--150. http:\/\/proceedings.mlr.press\/v132\/achddou21a.html"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-35389-6_2"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1405--1424","author":"Agrawal Shipra","year":"2014","unstructured":"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. SIAM, 1405--1424."},{"key":"e_1_3_2_1_4_1","unstructured":"Rui Ai Chang Wang Chenchen Li Jinshan Zhang Wenhan Huang and Xiaotie Deng. 2022. No-regret Learning in Repeated First-Price Auctions with Budget Constraints."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_3_2_1_6_1","series-title":"SIAM journal on computing","volume-title":"2002 b. The nonstochastic multiarmed bandit problem","author":"Auer Peter","year":"2002","unstructured":"Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 2002 b. The nonstochastic multiarmed bandit problem. SIAM journal on computing, Vol. 32, 1 (2002), 48--77."},{"key":"e_1_3_2_1_7_1","volume-title":"Non-Quasi-Linear Agents in Quasi-Linear Mechanisms. In 12th Innovations in Theoretical Computer Science Conference (ITCS","author":"Babaioff Moshe","year":"2021","unstructured":"Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. 2021. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_8_1","volume-title":"Learning to Bid in Contextual First Price Auctions. CoRR","author":"Badanidiyuru Ashwinkumar","year":"2021","unstructured":"Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. 2021. Learning to Bid in Contextual First Price Auctions. CoRR, Vol. abs\/2109.03173 (2021). showeprint[arXiv]2109.03173"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164539"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daum\u00e9 III and Aarti Singh (Eds.)","volume":"119","author":"Balseiro Santiago","year":"2020","unstructured":"Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2020. Dual Mirror Descent for Online Allocation Problems. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daum\u00e9 III and Aarti Singh (Eds.), Vol. 119. PMLR, 613--628."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467607"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2018.3174"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Amir Beck. 2017. First-order methods in optimization. SIAM.","DOI":"10.1137\/1.9781611974997"},{"key":"e_1_3_2_1_14_1","volume-title":"Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints. arXiv preprint arXiv:2405.16118","author":"Bernasconi Martino","year":"2024","unstructured":"Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. 2024. Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints. arXiv preprint arXiv:2405.16118 (2024)."},{"key":"e_1_3_2_1_15_1","volume-title":"Large deviations for martingales. Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics","author":"Blackwell D","year":"1997","unstructured":"D Blackwell. 1997. Large deviations for martingales. Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics (1997), 89--91."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242644"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_2_1_18_1","volume-title":"A Unifying Framework for Online Optimization with Long-Term Constraints. arXiv preprint arXiv:2209.07454","author":"Castiglioni Matteo","year":"2022","unstructured":"Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. 2022. A Unifying Framework for Online Optimization with Long-Term Constraints. arXiv preprint arXiv:2209.07454 (2022)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512061"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645660"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450052"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284177"},{"key":"e_1_3_2_1_25_1","first-page":"1","article-title":"Online mirror descent and dual averaging: keeping pace in the dynamic case","volume":"23","author":"Fang Huang","year":"2022","unstructured":"Huang Fang, Nicholas JA Harvey, Victor S Portella, and Michael P Friedlander. 2022. Online mirror descent and dual averaging: keeping pace in the dynamic case. Journal of Machine Learning Research, Vol. 23, 121 (2022), 1--38.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583491"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219208"},{"key":"e_1_3_2_1_28_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory. PMLR, 1755--1795","author":"Gangrade Aditya","year":"2024","unstructured":"Aditya Gangrade, Tianrui Chen, and Venkatesh Saligrama. 2024. Safe Linear Bandits over Unknown Polytopes. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 1755--1795."},{"key":"e_1_3_2_1_29_1","volume-title":"Bidding Agent Design in the LinkedIn Ad Marketplace. arXiv preprint arXiv:2202.12472","author":"Gao Yuan","year":"2022","unstructured":"Yuan Gao, Kaiyu Yang, Yuanlong Chen, Min Liu, and Noureddine El Karoui. 2022. Bidding Agent Design in the LinkedIn Ad Marketplace. arXiv preprint arXiv:2202.12472 (2022)."},{"key":"e_1_3_2_1_30_1","volume-title":"Jason Cheuk Nam Liang, and Vahab Mirrokni","author":"Golrezaei Negin","year":"2021","unstructured":"Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. 2021. Bidding and Pricing in Budget and ROI Constrained Markets. arXiv preprint arXiv:2107.07725 (2021)."},{"key":"e_1_3_2_1_31_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). arxiv: 2007.04568"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00022"},{"volume-title":"Auction Theory","author":"Krishna V.","key":"e_1_3_2_1_33_1","unstructured":"V. Krishna. 2002. Auction Theory. Elsevier Science."},{"volume-title":"Auction theory","author":"Krishna Vijay","key":"e_1_3_2_1_34_1","unstructured":"Vijay Krishna. 2009. Auction theory. Academic press."},{"volume-title":"Bandit algorithms","author":"Lattimore Tor","key":"e_1_3_2_1_35_1","unstructured":"Tor Lattimore and Csaba Szepesv\u00e1ri. 2020. Bandit algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501040.2501979"},{"key":"e_1_3_2_1_37_1","first-page":"24075","article-title":"An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints","volume":"34","author":"Liu Xin","year":"2021","unstructured":"Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. 2021. An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints. Advances in Neural Information Processing Systems, Vol. 34 (2021), 24075--24086.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_38_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory. PMLR, 3642--3643","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 The Thirty Seventh Annual Conference on Learning Theory. PMLR, 3642--3643."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503322"},{"key":"e_1_3_2_1_40_1","volume-title":"Stochastic convex optimization with multiple objectives. Advances in neural information processing systems","author":"Mahdavi Mehrdad","year":"2013","unstructured":"Mehrdad Mahdavi, Tianbao Yang, and Rong Jin. 2013. Stochastic convex optimization with multiple objectives. Advances in neural information processing systems, Vol. 26 (2013)."},{"key":"e_1_3_2_1_41_1","article-title":"Online Learning with Sample Path Constraints","volume":"10","author":"Mannor Shie","year":"2009","unstructured":"Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. 2009. Online Learning with Sample Path Constraints. Journal of Machine Learning Research, Vol. 10, 3 (2009).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000077"},{"key":"e_1_3_2_1_43_1","volume-title":"Advances in Neural Information Processing Systems","volume":"28","author":"Neu Gergely","year":"2015","unstructured":"Gergely Neu. 2015. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, Vol. 28 (2015)."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449968"},{"key":"e_1_3_2_1_45_1","volume-title":"Contextual Bandits with Stage-wise Constraints. arXiv preprint arXiv:2401.08016","author":"Pacchiano Aldo","year":"2024","unstructured":"Aldo Pacchiano, Mohammad Ghavamzadeh, and Peter Bartlett. 2024. Contextual Bandits with Stage-wise Constraints. arXiv preprint arXiv:2401.08016 (2024)."},{"key":"e_1_3_2_1_46_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. PMLR, 4633--4656","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 The Thirty Sixth Annual Conference on Learning Theory. PMLR, 4633--4656."},{"key":"e_1_3_2_1_47_1","volume-title":"Mystique: A Budget Pacing System for Performance Optimization in Online Advertising. In Companion Proceedings of the ACM on Web Conference","author":"Stram Rotem","year":"2024","unstructured":"Rotem Stram, Rani Abboud, Alex Shtoff, Oren Somekh, Ariel Raviv, and Yair Koren. 2024. Mystique: A Budget Pacing System for Performance Optimization in Online Advertising. In Companion Proceedings of the ACM on Web Conference 2024. 433--442."},{"volume-title":"High-dimensional probability: An introduction with applications in data science","author":"Vershynin Roman","key":"e_1_3_2_1_48_1","unstructured":"Roman Vershynin. 2018. High-dimensional probability: An introduction with applications in data science. Vol. 47. Cambridge university press."},{"key":"e_1_3_2_1_49_1","volume-title":"Conference on Learning Theory. PMLR, 1562--1583","author":"Weed Jonathan","year":"2016","unstructured":"Jonathan Weed, Vianney Perchet, and Philippe Rigollet. 2016. Online learning in repeated auctions. In Conference on Learning Theory. PMLR, 1562--1583."},{"key":"e_1_3_2_1_50_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Yu Hao","year":"2017","unstructured":"Hao Yu, Michael Neely, and Xiaohan Wei. 2017. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/3455716.3455717"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219918"},{"key":"e_1_3_2_1_53_1","volume-title":"On kernelized multi-armed bandits with constraints. Advances in neural information processing systems","author":"Zhou Xingyu","year":"2022","unstructured":"Xingyu Zhou and Bo Ji. 2022. On kernelized multi-armed bandits with constraints. Advances in neural information processing systems, Vol. 35 (2022), 14--26. gr"}],"event":{"name":"WWW '25: The ACM Web Conference 2025","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"],"location":"Sydney NSW Australia","acronym":"WWW '25"},"container-title":["Proceedings of the ACM on Web Conference 2025"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696410.3714734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:41Z","timestamp":1750295921000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":53,"alternative-id":["10.1145\/3696410.3714734","10.1145\/3696410"],"URL":"https:\/\/doi.org\/10.1145\/3696410.3714734","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"}}]}}