{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:48:20Z","timestamp":1768337300901,"version":"3.49.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030171261","type":"print"},{"value":"9783030171278","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the agent interacts with the environment, she may realize that, with hindsight, she could have increased her reward by playing differently: this difference in outcomes constitutes her <jats:italic>regret value<\/jats:italic>. The agent may thus elect to follow a <jats:italic>regret- minimal<\/jats:italic> strategy. In this paper, it is shown that (1) there always exist regret-minimal strategies that are admissible\u2014a strategy being inadmissible if there is another strategy that always performs better; (2) computing the minimum possible regret or checking that a strategy is regret-minimal can be done in \"Equation missing\", disregarding the computational cost of numerical analysis (otherwise, this bound becomes \"Equation missing\").<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_8","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"133-149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Impatient May Use Limited Optimism to Minimize Regret"],"prefix":"10.1007","author":[{"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillermo A.","family":"P\u00e9rez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie","family":"van den Bogaard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1007\/3-540-45061-0_79","volume-title":"Automata, Languages and Programming","author":"L de Alfaro","year":"2003","unstructured":"de Alfaro, L., Henzinger, T.A., Majumdar, R.: Discounting the future in systems theory. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1022\u20131037. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_79"},{"issue":"5","key":"8_CR2","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987\u20132006 (2009). https:\/\/doi.org\/10.1137\/070697926","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/1721837.1721844","volume":"6","author":"B Aminof","year":"2010","unstructured":"Aminof, B., Kupferman, O., Lampert, R.: Reasoning about online algorithms with weighted automata. ACM Trans. Algorithms 6(2), 28:1\u201328:36 (2010). https:\/\/doi.org\/10.1145\/1721837.1721844","journal-title":"ACM Trans. Algorithms"},{"key":"8_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511973468","volume-title":"Lectures in Game Theory for Computer Scientists","author":"KR Apt","year":"2011","unstructured":"Apt, K.R., Gr\u00e4del, E.: Lectures in Game Theory for Computer Scientists. Cambridge University Press, New York (2011)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-30000-9_1","volume-title":"Language and Automata Theory and Applications","author":"R Brenguier","year":"2016","unstructured":"Brenguier, R., et al.: Non-zero sum games for reactive synthesis. In: Dediu, A.-H., Janou\u0161ek, J., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 3\u201323. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-30000-9_1"},{"key":"8_CR6","doi-asserted-by":"publisher","unstructured":"Brenguier, R., P\u00e9rez, G.A., Raskin, J.F., Sankur, O.: Admissibility in quantitative graph games. In: Lal, A., Akshay, S., Saurabh, S., Sen, S. (eds.) 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016. LIPIcs, Chennai, India, 13\u201315 December 2016, vol. 65, pp. 42:1\u201342:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2016.42","DOI":"10.4230\/LIPIcs.FSTTCS.2016.42"},{"key":"8_CR7","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Goharshady, A.K., Ibsen-Jensen, R., Velner, Y.: Ergodic mean-payoff games for the analysis of attacks in crypto-currencies. In: Schewe, S., Zhang, L. (eds.) 29th International Conference on Concurrency Theory, CONCUR 2018. LIPIcs, Beijing, China, 4\u20137 September 2018, vol. 118, pp. 11:1\u201311:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2018.11","DOI":"10.4230\/LIPIcs.CONCUR.2018.11"},{"issue":"1","key":"8_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jsco.1998.0242","volume":"27","author":"F Cucker","year":"1999","unstructured":"Cucker, F., Koiran, P., Smale, S.: A polynomial time algorithm for diophantine equations in one variable. J. Symb. Comput. 27(1), 21\u201329 (1999). https:\/\/doi.org\/10.1006\/jsco.1998.0242","journal-title":"J. Symb. Comput."},{"key":"8_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4054-9","volume-title":"Competitive Markov Decision Processes","author":"J Filar","year":"2012","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-1-4612-4054-9"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-642-15155-2_31","volume-title":"Mathematical Foundations of Computer Science 2010","author":"E Filiot","year":"2010","unstructured":"Filiot, E., Le Gall, T., Raskin, J.-F.: Iterated regret minimization in game graphs. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 342\u2013354. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_31"},{"key":"8_CR11","doi-asserted-by":"publisher","unstructured":"Filiot, E., Jecker, I., Lhote, N., P\u00e9rez, G.A., Raskin, J.F.: On delay and regret determinization of max-plus automata. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, 20\u201323 June 2017, pp. 1\u201312. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005096","DOI":"10.1109\/LICS.2017.8005096"},{"issue":"1","key":"8_CR12","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.geb.2011.05.012","volume":"74","author":"JY Halpern","year":"2012","unstructured":"Halpern, J.Y., Pass, R.: Iterated regret minimization: a new solution concept. Games Econ. Behav. 74(1), 184\u2013207 (2012). https:\/\/doi.org\/10.1016\/j.geb.2011.05.012","journal-title":"Games Econ. Behav."},{"key":"8_CR13","doi-asserted-by":"publisher","unstructured":"Hunter, P., P\u00e9rez, G.A., Raskin, J.F.: Minimizing regret in discounted-sum games. In: Talbot, J.M., Regnier, L. (eds.) 25th EACSL Annual Conference on Computer Science Logic, CSL 2016. LIPIcs, Marseille, France, 29 August\u20131 September 2016, vol. 62, pp. 30:1\u201330:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2016.30","DOI":"10.4230\/LIPIcs.CSL.2016.30"},{"issue":"1","key":"8_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00236-016-0268-z","volume":"54","author":"P Hunter","year":"2017","unstructured":"Hunter, P., P\u00e9rez, G.A., Raskin, J.F.: Reactive synthesis without regret. Acta Inf. 54(1), 3\u201339 (2017). https:\/\/doi.org\/10.1007\/s00236-016-0268-z","journal-title":"Acta Inf."},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M Jurdzinski","year":"1998","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP $$\\cap $$ co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00150-1","journal-title":"Inf. Process. Lett."},{"key":"8_CR16","volume-title":"Markov Decision Processes","author":"ML Puterman","year":"2005","unstructured":"Puterman, M.L.: Markov Decision Processes. Wiley-Interscience, New York (2005)"},{"key":"8_CR17","volume-title":"The Mathematics of Petri Nets","author":"C Reutenauer","year":"1990","unstructured":"Reutenauer, C.: The Mathematics of Petri Nets. Prentice-Hall Inc., Upper Saddle River (1990)"},{"issue":"10","key":"8_CR18","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. 39(10), 1095\u20131100 (1953)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00992698","volume":"8","author":"CJCH Watkins","year":"1992","unstructured":"Watkins, C.J.C.H., Dayan, P.: Technical note Q-learning. Mach. Learn. 8, 279\u2013292 (1992). https:\/\/doi.org\/10.1007\/BF00992698","journal-title":"Mach. Learn."},{"issue":"1&2","key":"8_CR20","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1&2), 343\u2013359 (1996). https:\/\/doi.org\/10.1016\/0304-3975(95)00188-3","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17127-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T19:25:43Z","timestamp":1757100343000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}