{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:37:06Z","timestamp":1757626626631,"version":"3.44.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032036384"},{"type":"electronic","value":"9783032036391"}],"license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-03639-1_1","type":"book-chapter","created":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T13:23:47Z","timestamp":1756646627000},"page":"3-20","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Limitations and\u00a0Possibilities of\u00a0Nash Regret Minimization in\u00a0Zero-Sum Matrix Games Under Noisy Feedback"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9142-6255","authenticated-orcid":false,"given":"Arnab","family":"Maiti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2054-2985","authenticated-orcid":false,"given":"Kevin","family":"Jamieson","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8936-0229","authenticated-orcid":false,"given":"Lillian J.","family":"Ratliff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,1]]},"reference":[{"issue":"5","key":"1_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3088510","volume":"64","author":"S Agrawal","year":"2017","unstructured":"Agrawal, S., Goyal, N.: Near-optimal regret bounds for thompson sampling. J. ACM (JACM) 64(5), 1\u201324 (2017)","journal-title":"J. ACM (JACM)"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"47","author":"P Auer","year":"2002","unstructured":"Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47, 235\u2013256 (2002)","journal-title":"Mach. Learn."},{"key":"1_CR3","first-page":"51","volume":"1","author":"HF Bohnenblust","year":"1950","unstructured":"Bohnenblust, H.F., Karlin, S., Shapley, L.S.: Solutions of discrete, two-person games. Contrib. Theor. Games 1, 51\u201372 (1950)","journal-title":"Contrib. Theor. Games"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Cai, Y., Daskalakis, C.: On minmax theorems for multiplayer games. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 217\u2013234. SIAM (2011)","DOI":"10.1137\/1.9781611973082.20"},{"key":"1_CR5","unstructured":"Cardoso, A.R., Abernethy, J., Wang, H., Xu, H.: Competing against Nash equilibria in adversarially changing zero-sum games. In: International Conference on Machine Learning, pp. 921\u2013930. PMLR (2019)"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Prediction, learning, and games. Cambridge university press (2006)","DOI":"10.1017\/CBO9780511546921"},{"key":"1_CR7","first-page":"18990","volume":"33","author":"X Chen","year":"2020","unstructured":"Chen, X., Peng, B.: Hedging in games: faster convergence of external and swap regrets. Adv. Neural. Inf. Process. Syst. 33, 18990\u201318999 (2020)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Deckelbaum, A., Kim, A.: Near-optimal no-regret algorithms for zero-sum games. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 235\u2013254. SIAM (2011)","DOI":"10.1137\/1.9781611973082.21"},{"issue":"1\u20132","key":"1_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1006\/game.1999.0738","volume":"29","author":"Y Freund","year":"1999","unstructured":"Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games Econ. Behav. 29(1\u20132), 79\u2013103 (1999)","journal-title":"Games Econ. Behav."},{"key":"1_CR10","unstructured":"Jamieson, K., Malloy, M., Nowak, R., Bubeck, S., lil\u2019ucb.: An optimal exploration algorithm for multi-armed bandits. In: Conference on Learning Theory, pp. 423\u2013439. PMLR (2014)"},{"key":"1_CR11","unstructured":"Jin, C., Liu, Q., Yu, T.: The power of exploiter: provable multi-agent RL in large state spaces. In: International Conference on Machine Learning, pp. 10251\u201310279. PMLR (2022)"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-642-34106-9_18","volume-title":"Algorithmic Learning Theory","author":"E Kaufmann","year":"2012","unstructured":"Kaufmann, E., Korda, N., Munos, R.: Thompson sampling: an asymptotically optimal finite-time analysis. In: Bshouty, N.H., Stoltz, G., Vayatis, N., Zeugmann, T. (eds.) ALT 2012. LNCS (LNAI), vol. 7568, pp. 199\u2013213. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34106-9_18"},{"key":"1_CR13","first-page":"1","volume":"17","author":"E Kaufmann","year":"2016","unstructured":"Kaufmann, E., Capp\u00e9, O., Garivier, A.: On the complexity of best arm identification in multi-armed bandit models. J. Mach. Learn. Res. 17, 1\u201342 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"1_CR14","unstructured":"Liu, Q., Wang, Y., Jin,C.: Learning Markov games with adversarial opponents: efficient algorithms and fundamental limits. In: International Conference on Machine Learning, pp. 14036\u201314053. PMLR (2022)"},{"key":"1_CR15","unstructured":"Maiti, A., Jamieson, K., Ratliff, L.: Instance-dependent sample complexity bounds for zero-sum matrix games. In: International Conference on Artificial Intelligence and Statistics, pp. 9429\u20139469. PMLR (2023)"},{"key":"1_CR16","unstructured":"Maiti, A., Jamieson, K., Ratliff, L.J.: On the limitations and possibilities of nash regret minimization in zero-sum matrix games under noisy feedback (2023). arXiv preprint arXiv:2306.13233"},{"key":"1_CR17","unstructured":"O\u2019Donoghue, B.: Tor Lattimore, and Ian Osband. Matrix games with bandit feedback. In: Uncertainty in Artificial Intelligence, pp. 279\u2013289. PMLR (2021)"},{"key":"1_CR18","unstructured":"Rakhlin, S., Sridharan, K.: Optimization, learning, and games with predictable sequences. Adv. Neural Inf. Process. Syst. 26 (2013)"},{"key":"1_CR19","unstructured":"Syrgkanis, V., Agarwal, A., Luo, H., Schapire, R.E.: Fast convergence of regularized learning in games. Adv. Neural Inf. Process. Syst. 28 (2015)"},{"key":"1_CR20","unstructured":"Tian, Y., Wang, Y., Yu, T., Sra, S.: Online learning in unknown Markov games. In: International Conference on Machine Learning, pp. 10279\u201310288. PMLR (2021)"},{"key":"1_CR21","unstructured":"Wei, C.Y., Lee, C.W., Zhang, M., Luo, H.: Linear last-iterate convergence in constrained saddle-point optimization. In: International Conference on Learning Representations (2021)"},{"key":"1_CR22","unstructured":"Zhang, M., Zhao, P., Luo, H., Zhou, Z.H.: No-regret learning in time-varying zero-sum games. In: International Conference on Machine Learning, pp. 26772\u201326808. PMLR (2022)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-03639-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T23:10:53Z","timestamp":1757459453000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-03639-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,1]]},"ISBN":["9783032036384","9783032036391"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-03639-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,9,1]]},"assertion":[{"value":"1 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bath","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}