{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:27Z","timestamp":1778231427742,"version":"3.51.4"},"reference-count":31,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>We consider general reinforcement learning under the average reward criterion in Markov decision processes (MDPs), when the learner\u2019s goal is not to learn an optimal policy, but accepts any policy whose average reward is above a given satisfaction level [Formula: see text]. We show that with this more modest objective, it is possible to give algorithms that only have constant regret with respect to the level [Formula: see text], provided that there is a policy above this level. This is a generalization of known results from the bandit setting to MDPs. Further, we present a more general algorithm that achieves the best of both worlds: If the optimal policy has average reward above [Formula: see text], this algorithm has bounded regret with respect to [Formula: see text]. On the other hand, if all policies are below [Formula: see text], then the expected regret with respect to the optimal policy is bounded as for the UCRL2 algorithm.<\/jats:p>\n                  <jats:p>Funding: Financial support from the Austrian Science Fund (FWF) [Grant TAI 590-N] is gratefully acknowledged.<\/jats:p>","DOI":"10.1287\/moor.2023.0275","type":"journal-article","created":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T10:55:23Z","timestamp":1746788123000},"page":"1097-1119","source":"Crossref","is-referenced-by-count":0,"title":["Online Regret Bounds for Satisficing in Markov Decision Processes"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8146-9764","authenticated-orcid":false,"given":"Hossein","family":"Hajiabolhassan","sequence":"first","affiliation":[{"name":"Institute of Human Genetics, Diagnostic and Research Center for Molecular Biomedicine, Medical University of Graz, 8010 Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6033-2208","authenticated-orcid":false,"given":"Ronald","family":"Ortner","sequence":"additional","affiliation":[{"name":"Lehrstuhl f\u00fcr Informationstechnologie, Montanuniversit\u00e4t Leoben, 8700 Leoben, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","unstructured":"Abernethy JD, Amin K, Zhu R (2016) Threshold bandits, with and without censored feedback.\n                      Advances in Neural Information Processing Systems\n                      , vol. 29 (Curran Associates, Red Hook, NY), 4889\u20134897."},{"key":"B2","unstructured":"Arumugam D, Roy BV (2021) Deciding what to learn: A rate-distortion approach.\n                      Proc. 38th Internat. Conf. Machine Learn. ICML 2021\n                      , Proceedings of Machine Learning Research, vol. 139 (PMLR, New York), 373\u2013382."},{"key":"B3","unstructured":"Arumugam D, Roy BV (2021) The value of information when deciding what to learn.\n                      Adv. Neural Inform. Processing Systems 34 Annu. Conf. Neural Inform. Processing Systems 2021 NeurIPS 2021\n                      (Curran Associates, Red Hook, NY), 9816\u20139827."},{"key":"B4","doi-asserted-by":"crossref","unstructured":"Arumugam D, Roy BV (2022) Deciding what to model: Value-equivalent sampling for reinforcement learning.\n                      Adv. Neural Inform. Processing Systems 35 Annu. Conf. Neural Information Processing Systems 2022 NeurIPS 2022\n                      (Curran Associates, Red Hook, NY), 9024\u20139044.","DOI":"10.52202\/068431-0656"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"B6","unstructured":"Balaji N, Kiefer S, Novotn\u00fd P, P\u00e9rez GA, Shirmohammadi M (2019) On the complexity of value iteration.\n                      46th Internat. Colloquium Automata Languages Program. ICALP 2019\n                      , LIPIcs, vol. 132 (Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 102:1\u2013102:15."},{"key":"B7","unstructured":"Bubeck S, Perchet V, Rigollet P (2013) Bounded regret in stochastic multi-armed bandits.\n                      COLT 2013 26th Annu. Conf. Learn. Theory\n                      , Proceedings of Machine Learning Research, vol. 30 (PMLR, New York), 122\u2013134."},{"key":"B8","unstructured":"Chen L, Jain R, Luo H (2022) Learning infinite-horizon average-reward Markov decision process with constraints.\n                      Internat. Conf. Machine Learn., ICML 2022\n                      , Proceedings of Machine Learning Research, vol. 162 (PMLR, New York), 3246\u20133270."},{"key":"B9","unstructured":"Dabbs B (2009) Markov chains and mixing times. University of Chicago VIGRE REU 1\u201320. Accessed May 5, 2025, https:\/\/math.uchicago.edu\/\u223cmay\/VIGRE\/VIGRE2009\/REUPapers\/Dabbs.pdf."},{"key":"B10","unstructured":"Ding D, Zhang K, Basar T, Jovanovic MR (2020) Natural policy gradient primal-dual method for constrained Markov decision processes.\n                      Adv. Neural Inform. Processing Systems 33 Annu. Conf. Neural Inform. Processing Systems 2020 NeurIPS 2020\n                      (Curran Associates, Red Hook, NY), 8378\u20138390."},{"key":"B11","unstructured":"Ding D, Wei X, Yang Z, Wang Z, Jovanovic MR (2021) Provably efficient safe exploration via primal-dual policy optimization.\n                      24th Internat. Conf. Artificial Intelligence Statist. AISTATS 2021\n                      , Proceedings of Machine Learning Research, vol. 130 (PMLR, New York), 3304\u20133312."},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.12.011"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0928"},{"key":"B14","doi-asserted-by":"crossref","unstructured":"Goodrich MA, Quigley M (2004) Satisficing Q-learning: Efficient learning in problems with dichotomous attributes.\n                      Proc. 2004 Internat. Conf. Machine Learn. Appl. ICMLA 2004\n                      (IEEE Computer Society, Washington, DC), 65\u201372.","DOI":"10.1109\/ICMLA.2004.1383495"},{"key":"B15","first-page":"1563","volume":"11","author":"Jaksch T","year":"2010","journal-title":"J. Machine Learn. Res."},{"key":"B16","doi-asserted-by":"crossref","unstructured":"Kalagarla KC, Jain R, Nuzzo P (2021) A sample-efficient algorithm for episodic finite-horizon MDP with constraints.\n                      35th AAAI Conf. Artificial Intelligence AAAI 2021, 33rd Conf. Innovative Appl. Artificial Intelligence IAAI 2021, 11th Sympos. Ed. Adv. Artificial Intelligence EAAI 2021\n                      (AAAI Press, Washington, DC), 8030\u20138037.","DOI":"10.1609\/aaai.v35i9.16979"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"B18","unstructured":"Liu T, Zhou R, Kalathil D, Kumar PR, Tian C (2021) Learning policies with zero or bounded constraint violation for constrained MDPs.\n                      Adv. Neural Inform. Processing Systems 34 Annu. Conf. Neural Inform. Processing Systems 2021 NeurIPS 2021\n                      (Curran Associates, Red Hook, NY), 17183\u201317193."},{"key":"B19","author":"Michel T","year":"2023","journal-title":"Trans. Machine Learn. Res."},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Ortner R, Maillard O, Ryabko D (2014) Selecting near-optimal approximate state representations in reinforcement learning.\n                      Proc. Algorithmic Learn. Theory 25th Internat. Conf. ALT 2014\n                      , Lecture Notes in Computer Science, vol. 8776 (Springer, Cham, Switzerland), 140\u2013154.","DOI":"10.1007\/978-3-319-11662-4_11"},{"key":"B21","unstructured":"Osband I, Roy BV (2017) Why is posterior sampling better than optimism for reinforcement learning?\n                      Proc. 34th Internat. Conf. Machine Learn. ICML 2017\n                      , Proceedings of Machine Learning Research, vol. 70 (PMLR, New York), 2701\u20132710."},{"key":"B22","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman ML","year":"2005"},{"key":"B23","unstructured":"Qiu S, Wei X, Yang Z, Ye J, Wang Z (2020) Upper confidence primal-dual reinforcement learning for CMDP with adversarial loss.\n                      Adv. Neural Inform. Processing Systems 33 Annu. Conf. Neural Inform. Processing Systems 2020 NeurIPS 2020\n                      (Curran Associates, Red Hook, NY), 15277\u201315287."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2644380"},{"key":"B25","unstructured":"Ruan H, Zhou S, Chen Z, Ho CP (2023) Robust satisficing MDPs.\n                      Internat. Conf. Machine Learn. ICML 2023\n                      , Proceedings of Machine Learning Research, vol. 202 (PMLR, New York), 29232\u201329258."},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1229"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2022.3203361"},{"key":"B28","unstructured":"Strens MJA (2000) A Bayesian framework for reinforcement learning.\n                      Proc. 17th Internat. Conf. Machine Learn. ICML 2000\n                      (Morgan Kaufmann, Burlington, MA), 943\u2013950."},{"key":"B29","unstructured":"Tarbouriech J, Pirotta M, Valko M, Lazaric A (2021) A provably efficient sample collection strategy for reinforcement learning.\n                      Adv. Neural Inform. Processing Systems 34 Annu. Conf. Neural Inform. Processing Systems 2021 NeurIPS 2021\n                      (Curran Associates, Red Hook, NY), 7611\u20137624."},{"key":"B30","unstructured":"Weissman T, Ordentlich E, Seroussi G, Verdu S, Weinberger MJ (2003) Inequalities for the L1 deviation of the empirical distribution. Information Theory Research Group HP Laboratories. Accessed April 19, 2025, http:\/\/shiftleft.com\/mirrors\/www.hpl.hp.com\/techreports\/2003\/HPL-2003-97R1.pdf."},{"key":"B31","unstructured":"Zheng L, Ratliff LJ (2020) Constrained upper confidence reinforcement learning.\n                      Proc. 2nd Annu. Conf. Learn. Dynam. Control L4DC 2020\n                      , Proceedings of Machine Learning Research, vol. 120 (PMLR, New York), 620\u2013629."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:24:00Z","timestamp":1778228640000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0275"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0275","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}